HMMT 二月 2017 · COMB 赛 · 第 6 题

HMMT February 2017 — COMB Round — Problem 6

Emily starts with an empty bucket. Every second, she either adds a stone to the bucket or removes a 1 stone from the bucket, each with probability . If she wants to remove a stone from the bucket and 2 1 the bucket is currently empty, she merely does nothing for that second (still with probability ). What 2 is the probability that after 2017 seconds her bucket contains exactly 1337 stones?

解析

Emily starts with an empty bucket. Every second, she either adds a stone to the bucket or removes a 1 stone from the bucket, each with probability . If she wants to remove a stone from the bucket and 2 1 the bucket is currently empty, she merely does nothing for that second (still with probability ). What 2 is the probability that after 2017 seconds her bucket contains exactly 1337 stones? Proposed by: Sam Korsky 2017 ( ) 340 Answer: 2017 2 Replace 2017 with n and 1337 with k and denote the general answer by f ( n, k ). I claim that f ( n, k ) = n ( n − k ) b c 2 . We proceed by induction on n . n 2 1 The claim is obviously true for n = 0 since f (0 , 0) = 1. Moreover, we have that f ( n, 0) = f ( n − 2 1 1 1 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.