HMMT 二月 2020 · 团队赛 · 第 1 题
HMMT February 2020 — Team Round — Problem 1
题目详情
英文原题
- [20] Let n be a positive integer. Define a sequence by a = 1, a = a , and a = a + a for
0 2 i +1 i 2 i +2 i i +1
each i ≥ 0. Determine, with proof, the value of a + a + a + · · · + a .n
0 1 2 2 − 1
n ( n +1)
解析
英文解析
- [20] Let n be a positive integer. Define a sequence by a = 1, a = a , and a = a + a for
0 2 i +1 i 2 i +2 i i +1
each i ≥ 0. Determine, with proof, the value of a + a + a + · · · + a .n
0 1 2 2 − 1
Proposed by: Kevin Renn
3 +1
Answer:
n 2
Solution 1: Note that a = 1 for all n by repeatedly applying a = a . Now let b =
2 − 1 2 i +1 i nna + a + a + · · · + a . Applying the given recursion to every term of b except a gives
0 1 2 2 − 1 n 0
b = a + a + a + a + · · · + ann 0 1 2 3 2 − 1
n n = a + a + a + · · · + a + a + a + · · · + a
0 2 4 2 − 2 1 3 2 − 1 = a + ( a + a ) + ( a + a ) + ( a + a ) + · · · + ( a n − 1 + a n − 1 )
0 0 1 1 2 2 3
2 − 2 2 − 1 + a + a + a + · · · + a n − 1
0 1 2
2 − 1 =3 a + 3 a + 3 a + · · · + 3 a n − 1 + 3 a n − 1 − a n − 1
0 1 2
2 − 2 2 − 1 2 − 1 =3 b − 1 .
n − 1
3 +1 n
Now we easily obtain b = by induction.
2 n
Solution 2: Define a binary string to be good if it is the null string or of the form 101010 . . . 10. Let cnbe the number of good subsequences of n when written in binary form. We see c = 1 and c = c
0 2 n +1 nbecause the trailing 1 in 2 n + 1 cannot be part of a good subsequence. Furthermore, c − c
2 n +2 n +1
equals the number of good subsequences of 2 n + 2 that use the trailing 0 in 2 n + 2. We will show that this number is exactly c .
Let s be a good subsequence of 2 n + 2 that contains the trailing 0. If s uses the last 1, remove bothn
′
the last 1 and the trailing 0 from s ; the result s will be a good subsequence of n . If s does not use the
′
last 1, consider the sequence s where the trailing 0 in 2 n + 2 is replaced by the last 0 in n (which is
′
at the same position as the last 1 in 2 n + 2.) The map s 7 → s can be seen to be a bijection, and thusc = c + c .
2 n +2 n n +1
Now it is clear that a = c for all n . Consider choosing each binary string between 0 and 2 − 1 nn nwith equal probability. The probability that a given subsequence of length 2 k is good is . There 1
2 k
( )2
are subsequences of length 2 k , so by linearity of expectation, the total expected number of goodn
2 ksubsequences is
( )
b n/ 2 cnn n n
∑
(1 + 1 / 2) + (1 − 1 / 2) 3 + 1
2 k = = .
2 k n +1
2 2 2
k =0
3 +1 nn n
This is equal to the average of a , . . . , a , therefore the sum a + · · · + a is .
0 2 − 1 0 2 − 1
n ( n +1)2