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.

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