1979 IMO Problems/Problem 6
Contents
[hide]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.
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
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 |