PUMaC 2012 · 组合（B 组） · 第 7 题

PUMaC 2012 — Combinatorics (Division B) — Problem 7

[ 7 ] 5 people stand in a line facing one direction. In every round, the person at the front moves m randomly to any position in the line, including the front or the end. Suppose that is the n expected number of rounds needed for the last person of the initial line to appear at the front of the line, where m and n are relatively prime positive integers. What is m + n ?

解析

Call the last person at the beginning A . If A is at i th position, for the next round, there is i − 1 chance that the first person remains in front of A , which means the position of A remains 5 the same. Otherwise, A ’s position advances by 1. Hence the expected number of rounds for A to move the position by 1 is ( ) ( ) ( ) ( )

∞ + ∞ + ∞ k − 1 k k ∑ ∑ ∑ i − 1 i − 1 i − 1 i − 1 1 − k = ( k + 1) − k 5 5 5 5 k =1 k =0 k =0 ( )
∞ k ∑ i − 1 1 5 = = = i − 1 5 5 − i + 1 1 − 5 k =0 5 − i +1 (Note that this is the expectation of a geometric distribution with parameter p = .) So 5 in order to move A to the front, the total expected number of rounds needed is 5 ∑ 5 5 5 5 5 125 = + + + = , 5 − i + 1 1 2 3 4 12 i =2 so the answer is 125 + 12 = 137 . Problem contributed by Xufan Zhang.