IMO 1986 SL 13

Origin: FRG

Problem

A particle moves from (0, 0) to (n, n) directed by a fair coin. For each head it moves one step east and for each tail it moves one step north. At (n, y), y < n, it stays there if a head comes up and at (x, n), x < n, it stays there if a tail comes up. Let k be a fixed positive integer. Find the probability that the particle needs exactly 2n+k tosses to reach (n, n).

Solution

Let us consider the infinite integer lattice and assume that having reached a point (x, n) or (n, y), the particle continues moving east and north fol- lowing the rules of the game. The required probability pk is equal to the probability of getting to one of the points E1(n, n + k), E2(n + k, n), but without passing through (n, n + k −1) or (n + k −1, n). Thus p is equal to the probability p1 of getting to E1(n, n + k) via D1(n −1, n + k) plus the probability p2 of getting to E2(n + k, n) via D2(n + k, n −1). Both p1 and p2 are easily seen to be equal to
2n+k−1 n−1  2−2n−k, and therefore p =
2n+k−1 n−1  2−2n−k+1.