Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 11:34, 5 August 2024

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.

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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1979_IMO_Problems/Problem_6&oldid=224515"