Difference between revisions of "2018 AIME I Problems/Problem 14"

(Solution)
(fix typo)
Line 14: Line 14:
 
\qquad p(0,y) = \begin{cases}
 
\qquad p(0,y) = \begin{cases}
 
1 & y \le 2 \
 
1 & y \le 2 \
0 & y > 3
+
0 & y > 2
 
\end{cases}
 
\end{cases}
 
</math>
 
</math>

Revision as of 16:00, 9 March 2018


Let $SP_1P_2P_3EP_4P_5$ 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

This is easily solved by recursion/dynamic programming. To simplify the problem somewhat, let us imagine the seven vertices on a line $E \leftrightarrow P_4 \leftrightarrow P_5 \leftrightarrow S \leftrightarrow P_1 \leftrightarrow P_2 \leftrightarrow P_3 \leftrightarrow E$. We can count the number of left/right (L/R) paths of length $\le 11$ that start at $S$ and end at either $P_4$ or $P_3$.

We can visualize the paths using the common grid counting method by starting at the origin $(0,0)$, so that a right (R) move corresponds to moving 1 in the positive $x$ direction, and a left (L) move corresponds to moving 1 in the positive $y$ direction. Because we don't want to move more than 2 units left or more than 3 units right, our path must not cross the lines $y = x+2$ or $y = x-3$. Letting $p(x,y)$ be the number of such paths from $(0,0)$ to $(x,y)$ under these constraints, we have the following base cases:

$p(x,0) = \begin{cases} 1 & x \le 3 \\ 0 & x > 3 \end{cases} \qquad p(0,y) = \begin{cases} 1 & y \le 2 \\ 0 & y > 2 \end{cases}$

and recursive step $p(x,y) = p(x-1,y) + p(x,y-1)$ for $x,y \ge 1$.

The filled in grid will look something like this, where the lower-left $1$ corresponds to the origin:

$\begin{tabular}{|c|c|c|c|c|c|c|c|} \hline 0 & 0 & 0 & 0 & \textbf{89} & & & \\ \hline 0 & 0 & 0 & \textbf{28} & 89 & & & \\ \hline 0 & 0 & \textbf{9} & 28 & 61 & 108 & 155 & \textbf{155} \\ \hline 0 & \textbf{3} & 9 & 19 & 33 & 47 & \textbf{47} & 0 \\ \hline \textbf{1} & 3 & 6 & 10 & 14 & \textbf{14} & 0 & 0 \\ \hline 1 & 2 & 3 & 4 & \textbf{4} & 0 & 0 & 0 \\ \hline 1 & 1 & 1 & \textbf{1} & 0 & 0 & 0 & 0 \\ \hline \end{tabular}$

The bolded numbers on the top diagonal represent the number of paths from $S$ to $P_4$ in 2, 4, 6, 8, 10 moves, and the numbers on the bottom diagonal represent the number of paths from $S$ to $P_3$ in 3, 5, 7, 9, 11 moves. We don't care about the blank entries or entries above the line $x+y = 11$. The total number of ways is $1+3+9+28+89+1+4+14+47+155 = \boxed{351}$.

(Solution by scrabbler94)

2018 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 13
Followed by
Problem 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png