1979 IMO Problems/Problem 6

Problem

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, \quad a_{2n}={(2+\sqrt2)^{n-1} - (2-\sqrt2)^{n-1} \over\sqrt2}.$

Solution

First the part $a_{2n-1}=0$ It's pretty obvious. Let's make a sequence $b$ of 1 and -1, setting 1 when the frog jumps left and -1 when it jumps right. If the frog would want to come to vertex E from vertex A, then $\sum b_{i}$ from $i =1$ to $i =2n-1$ should be equal to either 4 or -4. But this sum is odd, so we have $a_{2n-1}= 0$

Now the less obvious part. Let's name $f(X,y)$ the number of ways, in which we can come to vertex X in y moves.

Then $f(E,2n) = f(F,2n-1)+f(D, 2n-1) = f(C, 2n-2)+f(G, 2n-2) =$ $f(D, 2n-3)+f(B, 2n-3)+f(F, 2n-3)+f(H, 2n-3) =$ $2f(D, 2n-5)+2f(F, 2n-5)+4f(H,2n-5)+4f(B, 2n-5) =$ $4[ f(B,2n-5)+f(D, 2n-5)+f(F,2n-5)+f(H, 2n-5) ]-2 [ f(F,2n-5)+f(D,2n-5)] =$ $4f(E,2n-2)-2f(E,2n-4)$

Now we can find a solution to this recurrence or simply prove by induction the given answer.

This solution was posted and copyrighted by Myszon11. The original thread for this problem can be found here: [1]

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

SOLUTION 2 The given regular octagon is shown in Figure Since the number of edges in any path joining A and E is even, it is impossible to reach E from A in an odd number of jumps. Thus a2n – 1 = 0, for all n ≥ 1. It is obvious that a2 = 0. Also, as ABCDE and AHGFE are the only 2 different path of 4 jumps from A to E, we have a4 = 2. To find a recurrence relation for a2n

, we introduce a new

supplementary sequence (bn

) as follows. For each n ≥ 1, let bn be the number of paths of exactly n jumps from C (or G) to E. Starting at A there are 4 ways for the frog to move in the first 2 jumps, namely, A → B → A, A → H → A A → B → C, A → H → G. Thus, by definitions of (an

) and (bn )

a2n = 2a2n – 2 + 2b2n – 2 ...(1) On the other hand, starting at C, there are 3 ways for the frog to move in the next 2 jumps if it does not stop at E, namely, C → B → C, C → D → C, C → B → A. Thus, b2n = 2b2n – 2 + a2n – 2.....(2) We shall now solve the system of linear recurrence relation (1) and (2) From (1), b2(n – 1) = a2n – a2(n – 1) .....(3) Substituting (3) into (2) gives a2(n + 1) – a2n = a2n – 2a2(n – 1) + a2(n – 1) or a2(n + 1) – 4a2n

+ 2a2(n – 1) = 0....(4)

Let dn = a2n

. Then (4) may be written as

dn + 1 – 4dn

+ 2dn – 1 = 0 ...(5)

The characteristic equation of (5) is x 2 – 4x + 2 = 0 and its roots are 2 ± .root2 regards kislay kai

1979 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Question
All IMO Problems and Solutions

Page

Toolbox

Search

1979 IMO Problems/Problem 6

Problem

Solution

See Also