Art of Problem Solving
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

2018 AIME II Problems/Problem 8: Difference between revisions

← Older editNewer edit →
Ktong (talk | contribs)
46 edits
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 17:24, 25 March 2018

Problem

A frog is positioned at the origin of the coordinate plane. From the point $(x, y)$, the frog can jump to any of the points $(x + 1, y)$, $(x + 2, y)$, $(x, y + 1)$, or $(x, y + 2)$. Find the number of distinct sequences of jumps in which the frog begins at $(0, 0)$ and ends at $(4, 4)$.

Solution 1

We solve this problem by working backwards. Notice, the only points the frog can be on to jump to $(4,4)$ in one move are $(2,4),(3,4),(4,2),$ and $(4,3)$. This applies to any other point, thus we can work our way from $(0,0)$ to $(4,4)$, recording down the number of ways to get to each point recursively.

$(0,0): 1$

$(1,0)=(0,1)=1$

$(2,0)=(0, 2)=2$

$(3,0)=(0, 3)=3$

$(4,0)=(0, 4)=5$

$(1,1)=2$, $(1,2)=(2,1)=5$, $(1,3)=(3,1)=10$, $(1,4)=(4,1)= 20$

$(2,2)=14, (2,3)=(3,2)=32, (2,4)=(4,2)=71$

$(3,3)=84, (3,4)=(4,3)=207$

$(4,4)=2\cdot \left( (4,2)+(4,3)\right) = 2\cdot \left( 207+71\right)=2\cdot 278=\boxed{556}$

Solution 2 (Case Bashing)

We'll refer to the moves $(x + 1, y)$, $(x + 2, y)$, $(x, y + 1)$, and $(x, y + 2)$ as $R_1$, $R_2$, $U_1$, and $U_2$, respectively. Then the possible sequence of moves that will take the frog from $(0,0)$ to $(4,4)$ are all the permutations of $U_1U_1U_1U_1R_1R_1R_1R_1$, $U_2U_1U_1R_1R_1R_1R_1$, $U_1U_1U_1U_1R_2R_1R_1$, $U_2U_1U_1R_2R_1R_1$, $U_2U_2R_1R_1R_1R_1$, $U_1U_1U_1U_1R_2R_2$, $U_2U_2R_2R_1R_1$, $U_2U_1U_1R_2R_2$, and $U_2U_2R_2R_2$. We can reduce the number of cases using symmetry.

Case 1: $U_1U_1U_1U_1R_1R_1R_1R_1$

There are $\frac{8!}{4!4!} = 70$ possibilities for this case.

Case 2: $U_2U_1U_1R_1R_1R_1R_1$ or $U_1U_1U_1U_1R_2R_1R_1$

There are $2 \cdot \frac{7!}{4!2!} = 210$ possibilities for this case.

Case 3: $U_2U_1U_1R_2R_1R_1$

There are $\frac{6!}{2!2!} = 180$ possibilities for this case.

Case 4: $U_2U_2R_1R_1R_1R_1$ or $U_1U_1U_1U_1R_2R_2$

There are $2 \cdot \frac{6!}{2!4!} = 30$ possibilities for this case.

Case 5: $U_2U_2R_2R_1R_1$ or $U_2U_1U_1R_2R_2$

There are $2 \cdot \frac{5!}{2!2!} = 60$ possibilities for this case.

Case 6: $U_2U_2R_2R_2$

There are $\frac{4!}{2!2!} = 6$ possibilities for this case.

Adding up all these cases gives us $70+210+180+30+60+6=\boxed{556}$ 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

These problems are copyrighted © by the Mathematical Association of America.

Retrieved from "https://wiki.aopstest.com/wiki/index.php?title=2018_AIME_II_Problems/Problem_8&oldid=93494"