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"

(Changed formatting for Solution 1, added Solution 2)
m (→‎Solution 2 (Case Bashing))
Line 25: Line 25:
  
 
==Solution 2 (Case Bashing)==
 
==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.
+
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 sequences 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>
 
Case 1: <math>U_1U_1U_1U_1R_1R_1R_1R_1</math>

Revision as of 17:28, 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 sequences 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=93495"