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 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 $(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

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_II_Problems/Problem_8&oldid=93494"