HMMT 十一月 2010 · GEN1 赛 · 第 2 题
HMMT November 2010 — GEN1 Round — Problem 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
解析
- [ 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 } , at least one of the a must be equal to 0. If we can find i, j ∈ { 2 , 3 , ..., 7 } such that a = a = 0 and n i j i < j , then the terms a a , a a , and a a will all be equal to 0. We did not count any term i − 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 because we can have only two. Thus, we can find at most one n ∈ { 2 , 3 , ..., 7 } such that a = 0. We will do n casework on which n in this range have a = 0. n 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 i of these equations for i 6 = n , then we must have a = 1 for all i 6 = n , so we have 1 possibility for each i choice of n and thus 4 possibilities total for this case. 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 have 8 another 2 possibilities. Finally, if a = 1 for n ∈ { 2 , 3 , ..., 7 } , then we will have a a = a a = ... = a a = 1. We already n 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.