1979 IMO Problems/Problem 6
Let and be opposite vertices of an octagon. A frog starts at vertex From any vertex except it jumps to one of the two adjacent vertices. When it reaches it stops. Let be the number of distinct paths of exactly jumps ending at . Prove that:
First the part It's pretty obvious. Let's make a sequence 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 from to should be equal to either 4 or -4. But this sum is odd, so we have
Now the less obvious part. Let's name the number of ways, in which we can come to vertex X in y moves.
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: 
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|
|1 • 2 • 3 • 4 • 5 • 6||Followed by|
|All IMO Problems and Solutions|