HMMT 十一月 2019 · 团队赛 · 第 7 题

HMMT November 2019 — Team Round — Problem 7

[55] Consider sequences a of the form a = ( a , a , . . . , a ) such that each term a is either 0 or 1. For 1 2 20 i each such sequence a , we can produce a sequence b = ( b , b , . . . , b ) , where 1 2 20   a + a i = 1 i i +1  b = a + a + a 1 < i < 20 i i − 1 i i +1   a + a i = 20 . i − 1 i How many sequences b are there that can be produced by more than one distinct sequence a ? − →

解析

[55] Consider sequences a of the form a = ( a , a , . . . , a ) such that each term a is either 0 or 1. For 1 2 20 i each such sequence a , we can produce a sequence b = ( b , b , . . . , b ) , where 1 2 20   a + a i = 1 i i +1  b = a + a + a 1 < i < 20 i i − 1 i i +1   a + a i = 20 . i − 1 i 2 How many sequences b are there that can be produced by more than one distinct sequence a ? Proposed by: Benjamin Qi Answer: 64 ˆ ˆ ˆ ˆ Let the two sequences be b and b . Then, observe that given a , if b = b and b = b , then b = b (since a 1 1 2 2 ˆ ˆ will uniquely determine the remaining elements in b and b ). Thus, b and b must start with (1 , 0 , . . . ) and (0 , 1 , . . . ), respectively (without loss of generality). ˆ ˆ Note that a is either 1 (in which case b = b = 0) or 2 (in which case b = b = 1). Moreover, b , b 3 3 3 3 3 4 5 ˆ must be the same as b , b (and the same for b ) for the sequences to generate the same a , a . We can 1 2 3 4 then pick a , a , . . . . 6 9 ˆ Observe, that the last elements also have to be ( . . . , 1 , 0) for b and ( . . . , 0 , 1) for b . Thus, the answer is k nonzero only for sequence lengths of 2 (mod 3), in which case, our answer is 2 , where the length is 3 k + 2 (since we have two choices for every third element). 6 Here, since N = 20 = 3(6) + 2, the answer is 2 = 64. − →