HMMT 二月 2017 · COMB 赛 · 第 6 题

英文解析

6. Emily starts with an empty bucket. Every second, she either adds a stone to the bucket or removes astone from the bucket, each with probability . If she wants to remove a stone from the bucket and 1
   the bucket is currently empty, she merely does nothing for that second (still with probability ). What 12
   is the probability that after 2017 seconds her bucket contains exactly 1337 stones?2
   Proposed by: Sam Korsky
   2017
   ( )
   Answer:340
   2017
   Replace 2017 with n and 1337 with k and denote the general answer by f ( n, k ). I claim that f ( n, k ) =2
   ( n − k )nb c
   . We proceed by induction on n .2
   2 n
   The claim is obviously true for n = 0 since f (0 , 0) = 1. Moreover, we have that f ( n, 0) = f ( n −1
   1 1 12
   1 , 0) + f ( n − 1 , 1) and f ( n, k ) = f ( n − 1 , k − 1) + f ( n − 1 , k + 1) for k > 0 so the inductive step is
   2 2 2
   immediate by Pascal’s identity. This concludes the proof.