Difference between revisions of "1979 IMO Problems/Problem 6"
(Created page with "==Problem== Let <math>A</math> and <math>E</math> be opposite vertices of an octagon. A frog starts at vertex <math>A.</math> From any vertex except <math>E</math> it jumps to...") |
|||
Line 22: | Line 22: | ||
== See Also == {{IMO box|year=1979|num-b=5|after=Last Question}} | == See Also == {{IMO box|year=1979|num-b=5|after=Last Question}} | ||
+ | |||
+ | 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 |
Revision as of 12:34, 5 August 2024
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 |
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