Difference between revisions of "2018 AIME I Problems/Problem 14"
(→Solution 2) |
Mathkiddie (talk | contribs) (→Solution 3 (One page solution)) |
||
(19 intermediate revisions by 8 users not shown) | |||
Line 6: | Line 6: | ||
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>. | 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>. | ||
− | ==Solution== | + | ==Solution 1== |
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>. | 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>. | ||
Line 41: | Line 41: | ||
(Solution by scrabbler94) | (Solution by scrabbler94) | ||
− | |||
== Solution 2 == | == Solution 2 == | ||
Line 47: | Line 46: | ||
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>. | 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*} | <cmath>\begin{align*} | ||
− | E_n&=P_{3_{n-1}}+P_{ | + | E_n&=P_{3_{n-1}}+P_{4_{n-1}} \\ |
− | &=P_{2_{n-2}}+P_{ | + | &=P_{2_{n-2}}+P_{5_{n-2}} \\ |
− | &=P_{1_{n-3}}+P_{3_{n-3}}+S_{n-3}+P_{ | + | &=P_{1_{n-3}}+P_{3_{n-3}}+S_{n-3}+P_{4_{n-3}} \\ |
− | &=(P_{3_{n-3}}+P_{ | + | &=(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}+S_{n-3}+P_{1_{n-3}} \\ | ||
− | &=E_{n-2}+P_{1_{n-4}}+P_{ | + | &=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_{ | + | &=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_{ | + | &=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_{ | + | &=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-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} \\ | &=E_{n-1}+2E_{n-2}-E_{n-3} \\ | ||
Line 61: | Line 60: | ||
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>. | 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> | + | 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>. | Finally adding yields <math>\sum_{k=0}^{12}E_k=\boxed{351}</math>. | ||
Line 69: | Line 68: | ||
==Video Solution== | ==Video Solution== | ||
https://www.youtube.com/watch?v=uWNExJc3hok | https://www.youtube.com/watch?v=uWNExJc3hok | ||
− | |||
− | |||
− | |||
− | |||
− | |||
{{AIME box|year=2018|n=I|num-b=13|num-a=15}} | {{AIME box|year=2018|n=I|num-b=13|num-a=15}} | ||
{{MAA Notice}} | {{MAA Notice}} | ||
− | + | [[Category:Intermediate Combinatorics Problems]] | |
− | |||
− |
Latest revision as of 17:29, 22 December 2023
Problem
Let be a heptagon. A frog starts jumping at vertex
. From any vertex of the heptagon except
, the frog may jump to either of the two adjacent vertices. When it reaches vertex
, the frog stops and stays there. Find the number of distinct sequences of jumps of no more than
jumps that end at
.
Solution 1
This is easily solved by recursion/dynamic programming. To simplify the problem somewhat, let us imagine the seven vertices on a line . We can count the number of left/right (L/R) paths of length
that start at
and end at either
or
.
We can visualize the paths using the common grid counting method by starting at the origin , so that a right (R) move corresponds to moving 1 in the positive
direction, and a left (L) move corresponds to moving 1 in the positive
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
or
. Letting
be the number of such paths from
to
under these constraints, we have the following base cases:
and recursive step
for
.
The filled in grid will look something like this, where the lower-left corresponds to the origin:
The bolded numbers on the top diagonal represent the number of paths from to
in 2, 4, 6, 8, 10 moves, and the numbers on the bottom diagonal represent the number of paths from
to
in 3, 5, 7, 9, 11 moves. We don't care about the blank entries or entries above the line
. The total number of ways is
.
(Solution by scrabbler94)
Solution 2
Let denotes the number of sequences with length
that ends at
. Define similarly for the other vertices. We seek for a recursive formula for
.
Computing a few terms we have
,
,
,
, and
.
Using the formula yields ,
,
,
,
,
,
, and
.
Finally adding yields .
~ Nafer
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.