2018 AIME II Problems/Problem 8

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)=$ (2,0)=(0, 2)=2$$ (Error compiling LaTeX. Unknown error_msg)(3,0)=(0, 3)=3$$ (Error compiling LaTeX. Unknown error_msg)(4,0)=(0, 4)=5$$ (Error compiling LaTeX. Unknown error_msg)(1,1)=2 $,$ (1,2)=(2,1)=5 $,$ (1,3)=(3,1)=10 $,$ (1,4)=(4,1)= 20$$ (Error compiling LaTeX. Unknown error_msg)(2,2)=14, (2,3)=(3,2)=32, (2,4)=(4,2)=71$$ (Error compiling LaTeX. Unknown error_msg)(3,3)=84, (3,4)=(4,3)=207$$ (Error compiling LaTeX. Unknown error_msg)(4,4)=2\cdot \left( (4,2)+(4,3)\right) = 2\cdot \left( 207+71\right)=2\cdot 278=\boxed{556}$

Solution 2

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.

Page

Toolbox

Search

2018 AIME II Problems/Problem 8

Problem

Solution 1

Solution 2