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 ieach 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 − 1 i i +1 i
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 ieach 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 − 1 i i +1 i
a + a i = 20 .
i − 1 i
How many sequences b are there that can be produced by more than one distinct sequence a ?2
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ˆknonzero 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).
Here, since N = 20 = 3(6) + 2, the answer is 2 = 64.6 − →