HMMT 十一月 2014 · 团队赛 · 第 6 题
HMMT November 2014 — Team Round — Problem 6
题目详情
- [ 6 ] Find the number of strictly increasing sequences of nonnegative integers with the following prop- erties: • 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. 2014 2014
解析
- [ 6 ] Find the number of strictly increasing sequences of nonnegative integers with the following prop- erties: • 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 the n problem 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 . 2 Next, we show that a = a + a for all natural number n . We consider the second-to-last terms n +2 n +1 n of 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 will still satisfy the problem conditions, and hence is in A . Conversely, for a sequence in A , we could n +1 n +1 add n + 2 at the end of that sequence, and since n + 1 and n + 2 have different parities, the resulting sequence will be in A . Therefore, there is a one-to-one correspondence between the sequences in n +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, so the second-to-last term cannot exceed n − 1. When we substitute the last term ( n + 2) with n , the resulting sequence will satisfy the problem conditions and will be in A . Conversely, for a sequence in n A , we could substitute its last term n , with n + 2. As n and n + 2 have the same parity, the resulting n sequence 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 number n +2 n +1 n of all possible sequences having their last terms as 12 is a = 144. Note that the resulting sequence 12 ( a ) is none other than the Fibonacci numbers. n 2014 2014