IMO 1979 SL 9

Origin: FRG

Problem

Let S and F be two opposite vertices of a regular octagon. A counter starts at S and each second is moved to one of the two neigh- boring vertices of the octagon. The direction is determined by the toss of a coin. The process ends when the counter reaches F. We define an to be the number of distinct paths of duration n seconds that the counter may take to reach F from S. Prove that for n = 1, 2, 3, . . ., a2n−1 = 0, a2n = \sqrt 2(xn−1−yn−1), where x = 2 + \sqrt 2, y = 2 − \sqrt 2.

Solution

Let us number the vertices, starting from S and moving clockwise. In that case S = 1 and F = 5. After an odd number of moves to a neighboring point we can be only on an even point, and hence it follows that a2n−1 = 0 for all n \inN. Let us define respectively zn and wn as the number of paths from S to S in 2n moves and the number of paths from S to points 3 and 7 in 2n moves. We easily derive the following recurrence relations: a2n+2 = wn, wn+1 = 2wn + 2zn, zn+1 = 2zn + wn, n = 0, 1, 2, . . . . By subtracting the second equation from the third we get zn+1 = wn+1 − wn. By plugging this equation into the formula for wn+2 we get wn+2 − 4wn+1 +2wn = 0. The roots of the characteristic equation r2 −4r +2 = 0 are x = 2 + \sqrt 2 and y = 2 − \sqrt 2. From the conditions w0 = 0 and w1 = 2 we easily obtain a2n = wn−1 = (xn−1 −yn−1)/ \sqrt 2 .