HMMT 二月 2015 · COMB 赛 · 第 3 题

HMMT February 2015 — COMB Round — Problem 3

Starting with the number 0, Casey performs an infinite sequence of moves as follows: he chooses a 1 number from { 1 , 2 } at random (each with probability ) and adds it to the current number. Let p m 2 be the probability that Casey ever reaches the number m . Find p − p . 20 15

解析

Starting with the number 0, Casey performs an infinite sequence of moves as follows: he chooses a 1 number from { 1 , 2 } at random (each with probability ) and adds it to the current number. Let p m 2 be the probability that Casey ever reaches the number m . Find p − p . 20 15 11 Answer: We note that the only way n does not appear in the sequence is if n − 1 and then n +1 20 2 ( ) 1 2 1 2 appears. Hence, we have p = 1, and p = 1 − p for n > 0. This gives p − = − p − , 0 n n − 1 n n − 1 2 3 2 3 so that ( ) n 2 1 1 p = + · − , n 3 3 2 so p − p is just 20 15 5 1 − ( − 2) 11 = . 20 20 3 · 2 2