HMMT 十一月 2010 · 冲刺赛 · 第 12 题

HMMT November 2010 — Guts Round — Problem 12

[ 8 ] An ant starts at the origin of a coordinate plane. Each minute, it either walks one unit to the right or one unit up, but it will never move in the same direction more than twice in the row. In how many different ways can it get to the point (5 , 5)?

解析

[ 8 ] An ant starts at the origin of a coordinate plane. Each minute, it either walks one unit to the right or one unit up, but it will never move in the same direction more than twice in the row. In how many different ways can it get to the point (5 , 5)? Answer: 84 We can change the ant’s sequence of moves to a sequence a , a , . . . , a , with a = 0 if 1 2 10 i the i -th step is up, and a = 1 if the i -th step is right. We define a subsequence of moves a , a , . . . , a , i i i +1 j ( i ≤ j ) as an up run if all terms of the subsequence are equal to 0, and a and a either do not i − 1 j +1 exist or are not equal to 0, and define a right run similarly. In a sequence of moves, up runs and right runs alternate, so the number of up rights can differ from the number of right runs by at most one. Now let f ( n ) denote the number of sequences a , a , . . . , a where a ∈ { 1 , 2 } for 1 ≤ i ≤ n , and 1 2 n i a + a + · · · + a = 5. (In essence, we are splitting the possible 5 up moves into up runs, and we are 1 2 n doing the same with the right moves). We can easily compute that f (3) = 3 , f (4) = 4 , f (5) = 1, and f ( n ) = 0 otherwise. For each possible pair of numbers of up runs and right runs, we have two choices of which type of run is 2 2 2 first. Our answer is then 2( f (3) + f (3) f (4) + f (4) + f (4) f (5) + f (5) ) = 2(9 + 12 + 16 + 4 + 1) = 84.