IMO 1979 · Problem 6

Let \(A\) and \(E\) be opposite vertices of a regular octagon. A frog starts jumping at vertex \(A\). From any vertex of the octagon except \(E\), it may jump to either of the two adjacent vertices. When it reaches vertex \(E\), the frog stops and stays there.. Let \(a_n\) be the number of distinct paths of exactly \(n\) jumps ending at \(E\). Prove that \(a_{2n-1}=0\), \[ a_{2n}=\frac{1}{\sqrt2}(x^{n-1}-y^{n-1}),\ n=1,2,3,\cdots, \] where \(x=2+\sqrt2\) and \(y=2-\sqrt2\).

Note. A path of \(n\) jumps is a sequence of vertices \((P_0,\ldots,P_n)\) such that
(i) \(P_0=A,\ P_n=E\);
(ii) for every \(i,\ 0\le i\le n-1,\ P_i\) is distinct from \(E\);
(iii) for every \(i,\ 0\le i\le n-1,\ P_i\) and \(P_{i+1}\) are adjacent.

Official text of the problem. Official problem paper (PDF)

Solution

Label the vertices \(A,B,C,D,E,F,G,H\) in cyclic order. Every jump switches between the sets \[ \{A,C,E,G\}\qquad\text{and}\qquad\{B,D,F,H\}. \] Since \(A\) and \(E\) belong to the same set, a path from \(A\) to \(E\) has even length. Hence \[ a_{2n-1}=0\qquad(n\ge1). \]

For each integer \(m\ge0\), consider partial paths starting at \(A\), making exactly \(2m\) jumps, and never visiting \(E\). Let \(u_m\) count those ending at \(A\), and let \(v_m\) count those ending at either \(C\) or \(G\). These are all possible endpoints, by the parity observation. Initially, \[ u_0=1,\qquad v_0=0. \]

We count extensions by two jumps that continue to avoid \(E\):

  • From \(A\), there are two extensions ending at \(A\), namely \(ABA\) and \(AHA\), and two ending at \(C\) or \(G\), namely \(ABC\) and \(AHG\).
  • From \(C\), there is one extension ending at \(A\), namely \(CBA\), and two ending at \(C\), namely \(CBC\) and \(CDC\). The remaining extension, \(CDE\), reaches \(E\).
  • From \(G\), the corresponding extensions are \(GHA\), \(GHG\), \(GFG\), and \(GFE\).

Every extended path has a unique prefix of length \(2m\). Consequently, \[ u_{m+1}=2u_m+v_m,\qquad v_{m+1}=2u_m+2v_m. \tag{1} \]

Moreover, every partial path counted by \(v_m\) has exactly one two-jump extension reaching \(E\): through \(D\) from \(C\), or through \(F\) from \(G\). Conversely, every admissible path reaching \(E\) after exactly \(2m+2\) jumps has such a prefix. Thus \[ a_{2m+2}=v_m\qquad(m\ge0). \tag{2} \]

Eliminating \(u_m\) from (1), we obtain \[ \begin{aligned} v_{m+2} &=2u_{m+1}+2v_{m+1}\\ &=4u_m+2v_m+2v_{m+1}\\ &=4v_{m+1}-2v_m. \end{aligned} \] The initial values are \(v_0=0\) and \(v_1=2\).

Now \(x=2+\sqrt2\) and \(y=2-\sqrt2\) both satisfy \[ t^2=4t-2. \] Therefore the sequence \[ w_m=\frac{x^m-y^m}{\sqrt2} \] satisfies \(w_{m+2}=4w_{m+1}-2w_m\). Also, \[ w_0=0,\qquad w_1=\frac{x-y}{\sqrt2}=2. \] Induction gives \(v_m=w_m\) for every \(m\ge0\). Substituting \(m=n-1\) into (2) yields \[ \boxed{a_{2n}=\frac{x^{n-1}-y^{n-1}}{\sqrt2}\qquad(n\ge1),} \] as required.

The solution was checked against John Scholes' IMO solution archive (Kalva).