Difference between revisions of "2018 AIME II Problems/Problem 8"
(→Solution) |
(Changed formatting for Solution 1, added Solution 2) |
||
Line 3: | Line 3: | ||
A frog is positioned at the origin of the coordinate plane. From the point <math>(x, y)</math>, the frog can jump to any of the points <math>(x + 1, y)</math>, <math>(x + 2, y)</math>, <math>(x, y + 1)</math>, or <math>(x, y + 2)</math>. Find the number of distinct sequences of jumps in which the frog begins at <math>(0, 0)</math> and ends at <math>(4, 4)</math>. | A frog is positioned at the origin of the coordinate plane. From the point <math>(x, y)</math>, the frog can jump to any of the points <math>(x + 1, y)</math>, <math>(x + 2, y)</math>, <math>(x, y + 1)</math>, or <math>(x, y + 2)</math>. Find the number of distinct sequences of jumps in which the frog begins at <math>(0, 0)</math> and ends at <math>(4, 4)</math>. | ||
− | ==Solution== | + | ==Solution 1== |
We solve this problem by working backwards. Notice, the only points the frog can be on to jump to <math>(4,4)</math> in one move are <math>(2,4),(3,4),(4,2),</math> and <math>(4,3)</math>. This applies to any other point, thus we can work our way from <math>(0,0)</math> to <math>(4,4)</math>, recording down the number of ways to get to each point recursively. | We solve this problem by working backwards. Notice, the only points the frog can be on to jump to <math>(4,4)</math> in one move are <math>(2,4),(3,4),(4,2),</math> and <math>(4,3)</math>. This applies to any other point, thus we can work our way from <math>(0,0)</math> to <math>(4,4)</math>, recording down the number of ways to get to each point recursively. | ||
+ | |||
<math>(0,0): 1</math> | <math>(0,0): 1</math> | ||
+ | |||
<math>(1,0)=(0,1)=1</math> | <math>(1,0)=(0,1)=1</math> | ||
+ | |||
<math>(2,0)=(0, 2)=2</math> | <math>(2,0)=(0, 2)=2</math> | ||
+ | |||
<math>(3,0)=(0, 3)=3</math> | <math>(3,0)=(0, 3)=3</math> | ||
+ | |||
<math>(4,0)=(0, 4)=5</math> | <math>(4,0)=(0, 4)=5</math> | ||
+ | |||
<math>(1,1)=2</math>, <math>(1,2)=(2,1)=5</math>, <math>(1,3)=(3,1)=10</math>, <math>(1,4)=(4,1)= 20</math> | <math>(1,1)=2</math>, <math>(1,2)=(2,1)=5</math>, <math>(1,3)=(3,1)=10</math>, <math>(1,4)=(4,1)= 20</math> | ||
+ | |||
<math>(2,2)=14, (2,3)=(3,2)=32, (2,4)=(4,2)=71</math> | <math>(2,2)=14, (2,3)=(3,2)=32, (2,4)=(4,2)=71</math> | ||
+ | |||
<math>(3,3)=84, (3,4)=(4,3)=207</math> | <math>(3,3)=84, (3,4)=(4,3)=207</math> | ||
+ | |||
<math>(4,4)=2\cdot \left( (4,2)+(4,3)\right) = 2\cdot \left( 207+71\right)=2\cdot 278=\boxed{556}</math> | <math>(4,4)=2\cdot \left( (4,2)+(4,3)\right) = 2\cdot \left( 207+71\right)=2\cdot 278=\boxed{556}</math> | ||
+ | ==Solution 2 (Case Bashing)== | ||
+ | We'll refer to the moves <math>(x + 1, y)</math>, <math>(x + 2, y)</math>, <math>(x, y + 1)</math>, and <math>(x, y + 2)</math> as <math>R_1</math>, <math>R_2</math>, <math>U_1</math>, and <math>U_2</math>, respectively. Then the possible sequence of moves that will take the frog from <math>(0,0)</math> to <math>(4,4)</math> are all the permutations of <math>U_1U_1U_1U_1R_1R_1R_1R_1</math>, <math>U_2U_1U_1R_1R_1R_1R_1</math>, <math>U_1U_1U_1U_1R_2R_1R_1</math>, <math>U_2U_1U_1R_2R_1R_1</math>, <math>U_2U_2R_1R_1R_1R_1</math>, <math>U_1U_1U_1U_1R_2R_2</math>, <math>U_2U_2R_2R_1R_1</math>, <math>U_2U_1U_1R_2R_2</math>, and <math>U_2U_2R_2R_2</math>. We can reduce the number of cases using symmetry. | ||
+ | |||
+ | Case 1: <math>U_1U_1U_1U_1R_1R_1R_1R_1</math> | ||
+ | |||
+ | There are <math>\frac{8!}{4!4!} = 70</math> possibilities for this case. | ||
+ | |||
+ | Case 2: <math>U_2U_1U_1R_1R_1R_1R_1</math> or <math>U_1U_1U_1U_1R_2R_1R_1</math> | ||
+ | |||
+ | There are <math>2 \cdot \frac{7!}{4!2!} = 210</math> possibilities for this case. | ||
+ | |||
+ | Case 3: <math>U_2U_1U_1R_2R_1R_1</math> | ||
+ | |||
+ | There are <math>\frac{6!}{2!2!} = 180</math> possibilities for this case. | ||
+ | |||
+ | Case 4: <math>U_2U_2R_1R_1R_1R_1</math> or <math>U_1U_1U_1U_1R_2R_2</math> | ||
+ | |||
+ | There are <math>2 \cdot \frac{6!}{2!4!} = 30</math> possibilities for this case. | ||
+ | |||
+ | Case 5: <math>U_2U_2R_2R_1R_1</math> or <math>U_2U_1U_1R_2R_2</math> | ||
+ | |||
+ | There are <math>2 \cdot \frac{5!}{2!2!} = 60</math> possibilities for this case. | ||
+ | |||
+ | Case 6: <math>U_2U_2R_2R_2</math> | ||
+ | |||
+ | There are <math>\frac{4!}{2!2!} = 6</math> possibilities for this case. | ||
+ | |||
+ | Adding up all these cases gives us <math>70+210+180+30+60+6=\boxed{556}</math> ways. | ||
{{AIME box|year=2018|n=II|num-b=7|num-a=9}} | {{AIME box|year=2018|n=II|num-b=7|num-a=9}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 18:24, 25 March 2018
Problem
A frog is positioned at the origin of the coordinate plane. From the point , the frog can jump to any of the points
,
,
, or
. Find the number of distinct sequences of jumps in which the frog begins at
and ends at
.
Solution 1
We solve this problem by working backwards. Notice, the only points the frog can be on to jump to in one move are
and
. This applies to any other point, thus we can work our way from
to
, recording down the number of ways to get to each point recursively.
,
,
,
Solution 2 (Case Bashing)
We'll refer to the moves ,
,
, and
as
,
,
, and
, respectively. Then the possible sequence of moves that will take the frog from
to
are all the permutations of
,
,
,
,
,
,
,
, and
. We can reduce the number of cases using symmetry.
Case 1:
There are possibilities for this case.
Case 2: or
There are possibilities for this case.
Case 3:
There are possibilities for this case.
Case 4: or
There are possibilities for this case.
Case 5: or
There are possibilities for this case.
Case 6:
There are possibilities for this case.
Adding up all these cases gives us ways.
2018 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
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.