PUMaC 2016 · 组合（A 组） · 第 6 题

PUMaC 2016 — Combinatorics (Division A) — Problem 6

The George Washington Bridge is 2016 meters long. Sally is standing on the George Wash- ington Bridge, 1010 meters from its left end. Each step, she either moves 1 meter to the left 1 or 1 meter to the right, each with probability . What is the expected number of steps she 2 will take to reach an end of the bridge?

解析

Note that the problem is symmetric in that if Sally stands at meter n or 2016 − n , the expected value of the number of steps to get off from those points are equal. Let E [ n ] be the expected value of the number of steps Sally will take starting at meter n (or 2016 − n ). Note that from meter 1008, Sally can either walk to meter 1007 or 1009. Thus E [1008] = 1 / 2( E [1007] + 1) + 1 / 2( E [1007] + 1) = E [1007] + 1 . We can create further recursive equations in this form. For example, E [1007] = 1 / 2( E [1006] + 1) + 1 / 2( E [1008] + 1) = 1 / 2( E [1006] + 1) + 1 / 2( E [1007] + 1 + 1) = ⇒ E [1007] = E [1006] + 3 . We leave the proof by induction to the reader that for all n ≤ 1008, E [ n ] = E [ n − 1] + (1 + 2(1008 − n )). This further leads to the fact that E [1] = 2015. Note that we are asked to compute E [1010] = E [1006]. Thus by addition of these recursions, we have 2 E [1006] = 2015 + 2013 + 2011 + · · · + 7 + 5 = 1008 − 1 − 3 = 1016060 . Problem written by Heesu Hwang.