返回题库

HMMT 二月 2020 · 团队赛 · 第 1 题

HMMT February 2020 — Team Round — Problem 1

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  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)
解析

英文解析

  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