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

HMMT February 2016 — Guts Round — Problem 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 does n before his number is zero or negative. Find the pair ( a, b ) such that lim ( E − an − b ) = 0 . n n →∞ 2

解析

[ 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 does n before his number is zero or negative. Find the pair ( a, b ) such that lim ( 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 2 Let F = E − n. By directly plugging this into the recurrence for E , we get the recurrence F = n n n n 3 1 1 ( 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 0 2 1 2 2 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 n Hence, E = n + − ( − ) , so lim ( E − n − ) = 0 . Hence ( , ) is the desired pair. n n →∞ n 3 9 9 2 3 9 3 9 2