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 n each i ≥ 0. Determine, with proof, the value of a + a + a + · · · + a . 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 n each i ≥ 0. Determine, with proof, the value of a + a + a + · · · + a . 0 1 2 2 − 1 Proposed by: Kevin Ren n 3 +1 Answer: 2 n Solution 1: Note that a = 1 for all n by repeatedly applying a = a . Now let b = 2 − 1 2 i +1 i n n a + a + a + · · · + a . Applying the given recursion to every term of b except a gives 0 1 2 2 − 1 n 0 n b = a + a + a + a + · · · + a n 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 n 3 +1 Now we easily obtain b = by induction. n 2 Solution 2: Define a binary string to be good if it is the null string or of the form 101010 . . . 10. Let c n be the number of good subsequences of n when written in binary form. We see c = 1 and c = c 0 2 n +1 n because 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 . n Let s be a good subsequence of 2 n + 2 that contains the trailing 0. If s uses the last 1, remove both ′ 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 thus c = c + c . 2 n +2 n n +1 n Now it is clear that a = c for all n . Consider choosing each binary string between 0 and 2 − 1 n n 1 with equal probability. The probability that a given subsequence of length 2 k is good is . There 2 k 2 ( ) n are subsequences of length 2 k , so by linearity of expectation, the total expected number of good 2 k subsequences is ( ) b n/ 2 c n n n n ∑ (1 + 1 / 2) + (1 − 1 / 2) 3 + 1 2 k = = . 2 k n +1 2 2 2 k =0 n 3 +1 n n This is equal to the average of a , . . . , a , therefore the sum a + · · · + a is . 0 2 − 1 0 2 − 1 2 n ( n +1)