1979 IMO Problems/Problem 6
Problem
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:
Solution
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.
Then
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.
See Also
1979 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |