2018 AIME I Problems/Problem 14

Let be a heptagon. A frog starts jumping at vertex S. From any vertex of the heptagon except E, the frog may jump to either of the two adjacent vertices. When it reaches vertex E, the frog stops and stays there. Find the number of distinct sequences of jumps of no more than 12 jumps that end at E.

Solution

(incomplete) Make a table:

\begin{center} \begin{tabular}{ ||c c c c c c c c c||}

\hline

Jump & E & P_3 & P_2 & P_1 & S & P_5 & P_4 & E \\ \hline \hline 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ \hline 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\

\hline

\end{tabular} \end{center}