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

PUMaC 2017 — Combinatorics (Division A) — Problem 6

Jackson begins at 1 on the number line. At each step, he remains in place with probability 85% and increases his position on the number line by 1 with probability 15%. Let d be his n 1 position on the number line after n steps, and let E be the expected value of . Find the n d n 1 least n such that > 2017. E n

解析

Let p be the probability of staying put (we will plug in later). Then we have 20 ( ) ( ) n n n +1 k n − k +1 ∑ ∑ p (1 − p ) n 1 k n − k k E = p (1 − p ) · = n k n − k + 1 (1 − p )( n + 1) k =0 k =0 ( ) ( ) n +1 n +1 k n − k +1 n +1 n +1 ∑ p (1 − p ) p 1 − p k = − = . (1 − p )( n + 1) (1 − p )( n + 1) (1 − p )( n + 1) k =0 17 Plugging in p = , we have 20 n +1 n +1 n +1 20 − 17 20 20 E = ≈ = . n n n 3( n + 1) · 20 3( n + 1) · 20 3( n + 1) 1 This becomes smaller than when 3( n + 1) becomes greater than 20 · 2017, i.e. n = 13446 . 2017 2