HMMT 十一月 2014 · 团队赛 · 第 6 题

英文解析

6. [ 6 ] Find the number of strictly increasing sequences of nonnegative integers with the following properties:
   • The first term is 0 and the last term is 12. In particular, the sequence has at least two terms.
   • Among any two consecutive terms, exactly one of them is even.
   Answer: 144 For a natural number n , let A be a set containing all sequences which satisfy thenproblem conditions but which 12 is replaced by n . Also, let a be the size of A .
   n n
   Team Round
   We first consider a and a . We get a = 1, as the only sequence satisfying the problem conditions is
   1 2 1
   0 , 1. We also get a = 1, as the only possible sequence is 0 , 1 , 2 .
   Next, we show that a = a + a for all natural number n . We consider the second-to-last terms 2
   n +2 n +1 nof each sequence in A .
   n +2
   Case 1. The second-to-last term is n + 1. When we leave out the last term, the remaining sequence willstill satisfy the problem conditions, and hence is in A . Conversely, for a sequence in A , we couldn +1 n +1
   add n + 2 at the end of that sequence, and since n + 1 and n + 2 have different parities, the resultingsequence will be in A . Therefore, there is a one-to-one correspondence between the sequences inn +2
   this case and the sequences in A . So the number of sequences in this case is a .
   n +1 n +1
   Case 2. The second-to-last term is less than or equal n . But n and n + 2 have the same parity, sothe second-to-last term cannot exceed n − 1. When we substitute the last term ( n + 2) with n , theresulting sequence will satisfy the problem conditions and will be in A . Conversely, for a sequence inn
   A , we could substitute its last term n , with n + 2. As n and n + 2 have the same parity, the resultingnsequence will be in A . Hence, in this case, the number of sequences is a .
   n n
   Now, since a = a + a for all natural numbers n , we can recursively compute that the numbern +2 n +1 nof all possible sequences having their last terms as 12 is a = 144. Note that the resulting sequence
   ( a ) is none other than the Fibonacci numbers.12
   2014 2014 n