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 "2018 AIME I Problems/Problem 14"
(→‎Solution 3)
 
(98 intermediate revisions by 17 users not shown)
Line 1: Line 1:
−
Let <math>SP_1P_2P_3EP_4P_5</math> 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==
+
==Problem==
−
(incomplete)
 
−
Make a table:
 
  
−
\begin{center}
+
 
−
\begin{tabular}{ |c|c|c|c|c|c|c|c|c| }  
+
 
−
\hline
+
Let <math>SP_1P_2P_3EP_4P_5</math> be a heptagon. A frog starts jumping at vertex <math>S</math>. From any vertex of the heptagon except <math>E</math>, the frog may jump to either of the two adjacent vertices. When it reaches vertex <math>E</math>, the frog stops and stays there. Find the number of distinct sequences of jumps of no more than <math>12</math> jumps that end at <math>E</math>.
−
Jump & E & P_3 & P_2 & P_1 & S & P_5 & P_4 & E \\
+
 
−
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
+
==Solution 1==
−
0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\
+
This is easily solved by recursion/dynamic programming. To simplify the problem somewhat, let us imagine the seven vertices on a line <math>E \leftrightarrow P_4 \leftrightarrow P_5 \leftrightarrow S \leftrightarrow P_1 \leftrightarrow P_2 \leftrightarrow P_3 \leftrightarrow E</math>. We can count the number of left/right (L/R) paths of length <math>\le 11</math> that start at <math>S</math> and end at either <math>P_4</math> or <math>P_3</math>.
−
\hline
+
 
 +
We can visualize the paths using the common grid counting method by starting at the origin <math>(0,0)</math>, so that a right (R) move corresponds to moving 1 in the positive <math>x</math> direction, and a left (L) move corresponds to moving 1 in the positive <math>y</math> 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 <math>y = x+2</math> or <math>y = x-3</math>. Letting <math>p(x,y)</math> be the number of such paths from <math>(0,0)</math> to <math>(x,y)</math> under these constraints, we have the following base cases:
 +
 
 +
<math>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}
 +
</math>
 +
 
 +
and recursive step
 +
<math>p(x,y) = p(x-1,y) + p(x,y-1)</math> for <math>x,y \ge 1</math>.
 +
 
 +
The filled in grid will look something like this, where the lower-left <math>1</math> corresponds to the origin:
 +
 
 +
<math>
 +
\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}
 
\end{tabular}
−
\end{center}
+
</math>
 +
 
 +
The bolded numbers on the top diagonal represent the number of paths from <math>S</math> to <math>P_4</math> in 2, 4, 6, 8, 10 moves, and the numbers on the bottom diagonal represent the number of paths from <math>S</math> to <math>P_3</math> in 3, 5, 7, 9, 11 moves. We don't care about the blank entries or entries above the line <math>x+y = 11</math>. The total number of ways is <math>1+3+9+28+89+1+4+14+47+155 = \boxed{351}</math>.
 +
 
 +
(Solution by scrabbler94)
 +
 
 +
== Solution 2 ==
 +
 
 +
Let <math>E_n</math> denotes the number of sequences with length <math>n</math> that ends at <math>E</math>. Define similarly for the other vertices. We seek for a recursive formula for <math>E_n</math>.
 +
<cmath>\begin{align*}
 +
E_n&=P_{3_{n-1}}+P_{4_{n-1}} \\
 +
&=P_{2_{n-2}}+P_{5_{n-2}} \\
 +
&=P_{1_{n-3}}+P_{3_{n-3}}+S_{n-3}+P_{4_{n-3}} \\
 +
&=(P_{3_{n-3}}+P_{4_{n-3}})+S_{n-3}+P_{1_{n-3}} \\
 +
&=E_{n-2}+S_{n-3}+P_{1_{n-3}} \\
 +
&=E_{n-2}+P_{1_{n-4}}+P_{5_{n-4}}+S_{n-4}+P_{2_{n-4}} \\
 +
&=E_{n-2}+(S_{n-4}+P_{1_{n-4}})+P_{5_{n-4}}+P_{2_{n-4}} \\
 +
&=E_{n-2}+(E_{n-1}-E_{n-3})+S_{n-5}+P_{4_{n-5}}+P_{1_{n-5}}+P_{3_{n-5}} \\
 +
&=E_{n-2}+(E_{n-1}-E_{n-3})+(S_{n-5}+P_{1_{n-5}})+(P_{4_{n-5}}+P_{3_{n-5}}) \\
 +
&=E_{n-2}+(E_{n-1}-E_{n-3})+(E_{n-2}-E_{n-4})+E_{n-4} \\
 +
&=E_{n-1}+2E_{n-2}-E_{n-3} \\
 +
\end{align*}</cmath>
 +
Computing a few terms we have <math>E_0=0</math>, <math>E_1=0</math>, <math>E_2=0</math>, <math>E_3=1</math>, and <math>E_4=1</math>.
 +
 
 +
Using the formula yields <math>E_5=3</math>, <math>E_6=4</math>, <math>E_7=9</math>, <math>E_8=14</math>, <math>E_9=28</math>, <math>E_{10}=47</math>, <math>E_{11}=89</math>, and <math>E_{12}=155</math>.
 +
 
 +
Finally adding yields <math>\sum_{k=0}^{12}E_k=\boxed{351}</math>.
 +
 
 +
~ Nafer
 +
 
 +
== Solution 3 ==
 +
For vertices <math>S, P_1, P_2, P_5,</math> the number of ways to get there after <math>n</math> jumps is the sum of the number of ways to get to the adjacent vertices after <math>n-1</math> jumps. For vertices <math>P_3,</math> and <math>P_4,</math> the number of ways to get there after <math>n</math> jumps is he number of ways to get to <math>P_2</math> and <math>P_5</math> after <math>n-1</math> jumps.
 +
 
 +
<math> \begin{tabular}{|l|c|c|c|c|c|c|c|}
 +
\hline
 +
Jump \# & \(S\)  & \(P_1\) & \(P_2\) & \(P_3\) & \(E\)        & \(P_4\) & \(P_5\) \\ \hline
 +
1      & 0      & 1      & 0      & 0      & \textbf{0}  & 0      & 1      \\ \hline
 +
2      & 2      & 0      & 1      & 0      & \textbf{0}  & 1      & 0      \\ \hline
 +
3      & 0      & 3      & 0      & 1      & \textbf{1}  & 0      & 3      \\ \hline
 +
4      & 6      & 0      & 4      & 0      & \textbf{1}  & 3      & 0      \\ \hline
 +
5      & 0      & 10      & 0      & 4      & \textbf{3}  & 0      & 9      \\ \hline
 +
6      & 19      & 0      & 14      & 0      & \textbf{4}  & 9      & 0      \\ \hline
 +
7      & 0      & 33      & 0      & 14      & \textbf{9}  & 0      & 28      \\ \hline
 +
8      & 61      & 0      & 47      & 0      & \textbf{14}  & 28      & 0      \\ \hline
 +
9      & 0      & 108    & 0      & 47      & \textbf{28}  & 0      & 89      \\ \hline
 +
10      & 197    & 0      & 155    & 0      & \textbf{47}  & 89      & 0      \\ \hline
 +
11      & 0      & 352    & 0      & 155    & \textbf{89}  & 0      & 286    \\ \hline
 +
12      & 638    & 0      & 507    & 0      & \textbf{155} & 286    & 0      \\ \hline
 +
\end{tabular} </math>
 +
 
 +
<math>0+0+1+1+3+4+9+14+28+47+89+155=\boxed{351}.</math>
 +
 
 +
==Video Solution==
 +
https://www.youtube.com/watch?v=uWNExJc3hok
 +
 
 +
{{AIME box|year=2018|n=I|num-b=13|num-a=15}}
 +
{{MAA Notice}}
 +
 
 +
[[Category:Intermediate Combinatorics Problems]]

Latest revision as of 19:45, 15 October 2024

Problem

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 1

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)

Solution 2

Let $E_n$ denotes the number of sequences with length $n$ that ends at $E$. Define similarly for the other vertices. We seek for a recursive formula for $E_n$. \begin{align*} E_n&=P_{3_{n-1}}+P_{4_{n-1}} \\ &=P_{2_{n-2}}+P_{5_{n-2}} \\ &=P_{1_{n-3}}+P_{3_{n-3}}+S_{n-3}+P_{4_{n-3}} \\ &=(P_{3_{n-3}}+P_{4_{n-3}})+S_{n-3}+P_{1_{n-3}} \\ &=E_{n-2}+S_{n-3}+P_{1_{n-3}} \\ &=E_{n-2}+P_{1_{n-4}}+P_{5_{n-4}}+S_{n-4}+P_{2_{n-4}} \\ &=E_{n-2}+(S_{n-4}+P_{1_{n-4}})+P_{5_{n-4}}+P_{2_{n-4}} \\ &=E_{n-2}+(E_{n-1}-E_{n-3})+S_{n-5}+P_{4_{n-5}}+P_{1_{n-5}}+P_{3_{n-5}} \\ &=E_{n-2}+(E_{n-1}-E_{n-3})+(S_{n-5}+P_{1_{n-5}})+(P_{4_{n-5}}+P_{3_{n-5}}) \\ &=E_{n-2}+(E_{n-1}-E_{n-3})+(E_{n-2}-E_{n-4})+E_{n-4} \\ &=E_{n-1}+2E_{n-2}-E_{n-3} \\ \end{align*} Computing a few terms we have $E_0=0$, $E_1=0$, $E_2=0$, $E_3=1$, and $E_4=1$.

Using the formula yields $E_5=3$, $E_6=4$, $E_7=9$, $E_8=14$, $E_9=28$, $E_{10}=47$, $E_{11}=89$, and $E_{12}=155$.

Finally adding yields $\sum_{k=0}^{12}E_k=\boxed{351}$.

~ Nafer

Solution 3

For vertices $S, P_1, P_2, P_5,$ the number of ways to get there after $n$ jumps is the sum of the number of ways to get to the adjacent vertices after $n-1$ jumps. For vertices $P_3,$ and $P_4,$ the number of ways to get there after $n$ jumps is he number of ways to get to $P_2$ and $P_5$ after $n-1$ jumps.

$\begin{tabular}{|l|c|c|c|c|c|c|c|} \hline Jump \# & \(S\) & \(P_1\) & \(P_2\) & \(P_3\) & \(E\) & \(P_4\) & \(P_5\) \\ \hline 1 & 0 & 1 & 0 & 0 & \textbf{0} & 0 & 1 \\ \hline 2 & 2 & 0 & 1 & 0 & \textbf{0} & 1 & 0 \\ \hline 3 & 0 & 3 & 0 & 1 & \textbf{1} & 0 & 3 \\ \hline 4 & 6 & 0 & 4 & 0 & \textbf{1} & 3 & 0 \\ \hline 5 & 0 & 10 & 0 & 4 & \textbf{3} & 0 & 9 \\ \hline 6 & 19 & 0 & 14 & 0 & \textbf{4} & 9 & 0 \\ \hline 7 & 0 & 33 & 0 & 14 & \textbf{9} & 0 & 28 \\ \hline 8 & 61 & 0 & 47 & 0 & \textbf{14} & 28 & 0 \\ \hline 9 & 0 & 108 & 0 & 47 & \textbf{28} & 0 & 89 \\ \hline 10 & 197 & 0 & 155 & 0 & \textbf{47} & 89 & 0 \\ \hline 11 & 0 & 352 & 0 & 155 & \textbf{89} & 0 & 286 \\ \hline 12 & 638 & 0 & 507 & 0 & \textbf{155} & 286 & 0 \\ \hline \end{tabular}$

$0+0+1+1+3+4+9+14+28+47+89+155=\boxed{351}.$

Video Solution

https://www.youtube.com/watch?v=uWNExJc3hok

2018 AIME I (Problems • Answer Key • Resources)
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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_14&oldid=229967"