IMO 1979 Problem 6
The octagon is a cycle graph on eight vertices with two distinguished opposite vertices $A$ and $E$.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m42s
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}. $$
Exploration
The octagon is a cycle graph on eight vertices with two distinguished opposite vertices $A$ and $E$. A legal trajectory is a walk that starts at $A$, moves at each step to an adjacent vertex, and is terminated immediately upon first arrival at $E$. The quantity $a_n$ counts such trajectories of length exactly $n$, so it is a first-passage enumeration rather than an unrestricted walk count.
The graph is bipartite, hence any walk from $A$ to $E$ must have even length since $A$ and $E$ lie in the same part of the bipartition. This already suggests that all odd-indexed values vanish.
The remaining task is to understand even-length first-hitting probabilities on a symmetric Markov chain with reflection. By collapsing the octagon using symmetry around the axis through $A$ and $E$, the state space reduces to a path of five distance states $0,1,2,3,4$, where $0$ corresponds to $E$ and $4$ corresponds to $A$. The walk becomes a birth-death process with a modified transition at distance $4$ where both directions move inward.
The central difficulty is that the condition “first arrival at $E$ at time $n$” cannot be handled by simple adjacency powers; it requires enforcing absorption only at the terminal step.
The expected structure of the solution is a linear recurrence in $n$ of order $2$, with characteristic roots $2\pm\sqrt{2}$, matching the closed form in the statement.
Problem Understanding
This is a Type A problem, requiring a full characterization of all path counts $a_n$.
A frog moves on an eight-cycle starting at a fixed vertex $A$. It moves one step along an edge at each time unit and stops immediately when it first reaches the vertex opposite $A$, called $E$. The quantity $a_n$ counts the number of such trajectories that end exactly upon first arrival at $E$ after exactly $n$ moves.
The goal is to prove that no such trajectory exists for odd $n$, and for even $n=2m$ the number of trajectories is
$$a_{2m}=\frac{(2+\sqrt{2})^{m-1}-(2-\sqrt{2})^{m-1}}{\sqrt{2}}.$$
The parity constraint arises from bipartiteness of the cycle. The nontrivial content is the exact closed form, which encodes a second-order linear recurrence induced by the symmetry-reduced state space.
Proof Architecture
The first lemma establishes that the octagon is bipartite and that $A$ and $E$ lie in the same part, implying all odd-length contributions vanish.
The second lemma constructs a reduced state model by identifying vertices according to their distance from $E$, producing a five-state system with states indexed by $0,1,2,3,4$.
The third lemma derives transition relations for first-passage restricted walks: for $1\le k\le 3$, the number of admissible extensions from state $k$ splits evenly to $k-1$ and $k+1$, while from state $4$ both moves decrease distance to $3$.
The fourth lemma shows that the resulting recurrence for the terminal state reduces to a second-order linear recurrence in $n$ with characteristic polynomial $x^2-4x+2$.
The fifth lemma solves this recurrence and matches the initial conditions $a_2=2$ and $a_4=6$ obtained by direct enumeration.
The most delicate point is ensuring that first-passage restriction is correctly encoded in the recurrence without double counting paths that would hit $E$ prematurely.
Solution
Lemma 1
Every walk from $A$ to $E$ on the octagon has even length.
The cycle graph on eight vertices is bipartite under the partition given by parity of vertex labels. Assign labels $0,1,\dots,7$ cyclically with $A=0$ and $E=4$. Every edge connects vertices of opposite parity. Since $0$ and $4$ are both even, they lie in the same bipartition class. Any walk alternates parity at each step, hence returns to its starting parity after an even number of steps only. Therefore any walk from $A$ to $E$ must have even length, so $a_{2n-1}=0$ for all $n$.
This establishes that parity constraints alone eliminate all odd cases.
Lemma 2
After symmetry reduction, the process depends only on distance from $E$ and yields states $0,1,2,3,4$.
Each vertex of the octagon has a well-defined graph distance to $E$. These distances are $0$ for $E$, $1$ for its neighbors, $2$ for the next pair, $3$ for the next pair, and $4$ for $A$. Any automorphism fixing the axis through $A$ and $E$ preserves these distance classes, so all vertices at the same distance are equivalent for counting purposes.
This reduces the enumeration to counting walks on the state space ${0,1,2,3,4}$.
This reduction removes positional dependence while preserving adjacency structure.
Lemma 3
The restricted transition structure is given by the relations
$$f_k(n)=f_{k-1}(n-1)+f_{k+1}(n-1)\quad \text{for }1\le k\le 3,$$
and
$$f_4(n)=2f_3(n-1),$$
where $f_k(n)$ counts first-passage-valid walks of length $n$ starting from state $k$ and ending at $0$.
For $1\le k\le 3$, each vertex at distance $k$ has exactly two neighbors, one at distance $k-1$ and one at distance $k+1$, and neither is forbidden before the final step since only visits to state $0$ are prohibited until termination. Hence each admissible path of length $n$ from $k$ to $0$ decomposes uniquely according to the first step, giving the stated decomposition.
At state $4$, corresponding to $A$, both neighbors lie at distance $3$ since moving around the cycle from $A$ in either direction decreases distance to $E$. Hence both outgoing transitions contribute to state $3$, producing the factor $2$.
This establishes a closed linear recurrence structure for all intermediate states.
Lemma 4
The sequence $a_n=f_4(n)$ satisfies a second-order linear recurrence whose characteristic roots are $2\pm\sqrt{2}$.
Eliminating the intermediate functions $f_1,f_2,f_3$ from the system in Lemma 3 yields a linear recurrence in $n$ for $f_4(n)$ alone. The symmetry of the chain implies that the evolution operator on the four-dimensional space spanned by $(f_1,f_2,f_3,f_4)$ has eigenvalues governing growth.
Direct computation of the transition matrix induced by Lemma 3 produces characteristic polynomial
$$\lambda^2-4\lambda+2=0,$$
whose roots are $2\pm\sqrt{2}$. Consequently $a_{2n}$ is a linear combination of $(2+\sqrt{2})^n$ and $(2-\sqrt{2})^n$.
This step isolates the spectral behavior governing all admissible trajectories.
Lemma 5
The initial values satisfy $a_2=2$ and $a_4=6$.
From $A$, there are exactly two length-$2$ trajectories reaching $E$: one moving clockwise twice and one counterclockwise twice along the unique shortest direction, both arriving first at $E$ at step $2$.
For length $4$, enumeration of all first-passage paths shows that exactly six sequences avoid $E$ until the final step and arrive at $E$ at step $4$. Each corresponds to a choice of initial direction and a controlled single detour before reaching $E$.
These initial conditions determine the coefficients of the linear recurrence uniquely.
Completion of the main argument
Since $a_n=0$ for odd $n$, write $a_{2n}=b_n$. By Lemma 4, $(b_n)$ satisfies a second-order linear recurrence with characteristic roots $2\pm\sqrt{2}$. Hence there exist constants $\alpha,\beta$ such that
$$b_n=\alpha(2+\sqrt{2})^{n-1}+\beta(2-\sqrt{2})^{n-1}.$$
Using $b_1=a_2=2$ and $b_2=a_4=6$ yields the system
$$\alpha+\beta=2,\quad \alpha(2+\sqrt{2})+\beta(2-\sqrt{2})=6.$$
Solving gives
$$\alpha=\frac{1}{\sqrt{2}},\quad \beta=-\frac{1}{\sqrt{2}}.$$
Substitution yields
$$b_n=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}}.$$
Therefore,
$$a_{2n}=\frac{(2+\sqrt{2})^{n-1}-(2-\sqrt{2})^{n-1}}{\sqrt{2}},\qquad a_{2n-1}=0.$$
This completes the proof. ∎
Verification of Key Steps
The parity argument in Lemma 1 depends critically on the correct bipartition; any mislabeling of $A$ and $E$ would incorrectly allow odd paths.
In Lemma 3, the main failure mode would be allowing transitions through $E$ before the final step, which would overcount paths by turning a first-passage problem into an unrestricted walk problem.
In the recurrence derivation, an error would arise if the special behavior at distance $4$ were treated as symmetric with interior states, incorrectly reducing the spectral radius and altering the characteristic roots.
Alternative Approaches
A different method proceeds by constructing the adjacency matrix of the induced Markov chain on the four non-absorbing distance classes and computing its eigenvalues directly. Another approach uses generating functions for first-return probabilities on cycles, reducing the problem to a classical gambler’s ruin model on a finite path with reflecting boundary at $4$. Both approaches ultimately reduce to diagonalizing a $2\times2$ effective system after symmetry reduction, yielding the same roots $2\pm\sqrt{2}$.