HMMT 二月 2016 · 冲刺赛 · 第 21 题

英文解析

21. [ 12 ] Tim starts with a number n , then repeatedly flips a fair coin. If it lands heads he subtracts 1
    from his number and if it lands tails he subtracts 2. Let E be the expected number of flips Tim doesnbefore his number is zero or negative. Find the pair ( a, b ) such thatlim ( E − an − b ) = 0 .
    n →∞n
    Proposed by:
    2 2
    Answer: ( , )
    3 9
    1 1 1
    We have the recurrence E = ( E + 1) + ( E + 1) , or E = 1 + ( E + E ) , for n ≥ 2 .
    n n − 1 n − 2 n n − 1 n − 2
    2 2 2
    Let F = E − n. By directly plugging this into the recurrence for E , we get the recurrence F =2
    n n n n
    1 13
    ( F + F ) . The roots of the characteristic polynomial of this recurrence are 1 and − , so F =
    n − 1 n − 1 n
    2 2
    1 n
    A + B ( − ) for some A and B depending on the initial conditions. But clearly we have E = 0 and
    1 2 220
    E = 1 so F = 0 and F = so A = and B = − .
    1 0 1
    3 9 9
    2 2 2 1 2 2 2 2
    Hence, E = n + − ( − ) , so lim ( E − n − ) = 0 . Hence ( , ) is the desired pair.nn n →∞ n
    3 9 9 2 3 9 3 9 2