HMMT 十一月 2010 · GEN1 赛 · 第 2 题

英文解析

2. [ 3 ] How many sequences a , a , . . . , a of zeroes and ones have a a + a a + · · · + a a = 5?
   1 2 8 1 2 2 3 7 8
   Answer: 9 First, note that we have seven terms in the left hand side, and each term can be either
   0 or 1, so we must have five terms equal to 1 and two terms equal to 0. Thus, for n ∈ { 1 , 2 , ..., 8 } , atleast one of the a must be equal to 0. If we can find i, j ∈ { 2 , 3 , ..., 7 } such that a = a = 0 andn i ji < j , then the terms a a , a a , and a a will all be equal to 0. We did not count any termi − 1 i i i +1 j j +1
   twice because i − 1 < i < j , so we would have three terms equal to 0, which cannot happen becausewe can have only two. Thus, we can find at most one n ∈ { 2 , 3 , ..., 7 } such that a = 0. We will docasework on which n in this range have a = 0.nn
   If n ∈ { 3 , 4 , 5 , 6 } , then we know that the terms a a = a a = 0, so all other terms must be 1,
   n − 1 n n n +1
   so a a = a a = ... = a a = 1 and a a = ... = a a = 1. Because every a appears in one
   1 2 2 3 n − 2 n − 1 n +1 n +2 7 8 iof these equations for i 6 = n , then we must have a = 1 for all i 6 = n , so we have 1 possibility for eachchoice of n and thus 4 possibilities total for this case.i
   If n = 2, then again we have a a = a a = 0, so we must have a a = a a = ... = a a = 1, so
   1 2 2 3 3 4 4 5 7 8
   a = a = ... = a = 1. However, this time a is not fixed, and we see that regardless of our choice of
   3 4 8 1
   a the sum will still be equal to 5. Thus, since there are 2 choices for a , then there are 2 possibilities
   1 1
   total for this case. The case where n = 7 is analogous, with a having 2 possibilities, so we haveanother 2 possibilities.8
   Finally, if a = 1 for n ∈ { 2 , 3 , ..., 7 } , then we will have a a = a a = ... = a a = 1. We alreadyn 2 3 3 4 6 7
   have five terms equal to 1, so the remaining two terms a a and a a must be 0. Since a = 1, then
   1 2 7 8 2
   we must have a = 0, and since a = 1 then a = 0. Thus, there is only 1 possibility for this case.
   1 7 8
   Summing, we have 4 + 2 + 2 + 1 = 9 total sequences.