IMO 1979/B3 solution

IMO 1979

Problem B3

Let A and E be opposite vertices of an octagon. A frog starts at vertex A. From any vertex except E it jumps to one of the two adjacent vertices. When it reaches E it stops. Let a_n be the number of distinct paths of exactly n jumps ending at E. Prove that:

a_2n-1 = 0
a_2n = (2 + √2)^n-1/√2 - (2 - √2)^n-1/√2.

Solution

Each jump changes the parity of the shortest distance to E. The parity is initially even, so an odd number of jumps cannot end at E. Hence a_2n-1 = 0.

We derive a recurrence relation for a_2n. This is not easy to do directly, so we introduce b_n which is the number of paths length n from C to E. Then we have immediately:

a_2n = 2a_2n-2 + 2b_2n-2 for n > 1
b_2n = 2b_2n-2 + a_2n-2 for n > 1

Hence, using the first equation: a_2n - 2a_2n-2 = 2a_2n-2 - 4a_2n-4 + 2b_2n-2 - 4b_2n-4 for n > 2. Using the second equation, this leads to: a_2n = 4a_2n-2 - 2a_2n-4 for n > 2. This is a linear recurrence relation with the general solution: a_2n = a(2 + √2)^n-1 + b(2 - √2)^n-1. But we easily see directly that a₄ = 2, a₆ = 8 and we can now solve for the coefficients to get the solution given.

Solutions are also available in Murray S Klamkin, International Mathematical Olympiads 1978-1985, MAA 1986, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

21st IMO 1979