Difference between revisions of "2018 AIME II Problems/Problem 8"

Revision as of 20:25, 6 October 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}$

A diagram of the numbers:

5 - 20 - 71 - 207 - $\boxed{556}$

3 - 10 - 32 - 84 - 207

2 - 5 - 14 - 32 - 71

1 - 2 - 5 - 10 - 20

1 - 1 - 2 - 3 - 5

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.

Solution 3 (General Case)

Mark the total number of distinct sequences of jumps for the frog to reach the point $(x,y)$ as $\varphi (x,y)$ . Consider for each point $(x,y)$ in the first quadrant, there are only $4$ possible points in the first quadrant for frog to reach point $(x,y)$ , and these 4 points are $(x-1,y); (x-2,y); (x,y-1); (x,y-2)$ . As a result, the way to count $\varphi (x,y)$ is $\varphi (x,y)=\varphi (x-1,y)+\varphi (x-2,y)+\varphi (x,y-1)+\varphi (x,y-2)$

Also, for special cases, $\varphi (0,y)=\varphi (0,y-1)+\varphi (0,y-2)$

$\varphi (x,0)=\varphi (x-1,0)+\varphi (x-2,0)$

$\varphi (x,1)=\varphi (x-1,1)+\varphi (x-2,1)+\varphi (x,0)$

$\varphi (1,y)=\varphi (1,y-1)+\varphi (1,y-2)+\varphi (0,y)$

$\varphi (1,1)=\varphi (1,0)+\varphi (0,1)$

Start with $\varphi (0,0)=1$ , use this method and draw the figure below, we can finally get $\varphi (4,4)=556$

(In order to make the LaTeX thing more beautiful to look at, I put $0$ to make every number a $3$ -digits number)

$005-020-071-207-\boxed{556}$ $003-010-032-084-207$ $002-005-014-032-071$ $001-002-005-010-020$ $001-001-002-003-005$

So the total number of distinct sequences of jumps for the frog to reach $(4,4)$ is $\boxed {556}$ .

~Solution by $BladeRunnerAUG$ (Frank FYC)

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.

@@ Line 65: / Line 65: @@
 Adding up all these cases gives us <math>70+210+180+30+60+6=\boxed{556}</math> ways.
-==Solution 3==
+==Solution 3 (General Case)==
 Mark the total number of distinct sequences of jumps for the frog to reach the point <math>(x,y)</math> as <math>\varphi (x,y)</math>. Consider for each point <math>(x,y)</math> in the first quadrant, there are only <math>4</math> possible points in the first quadrant for frog to reach point <math>(x,y)</math>, and these 4 points are <cmath>(x-1,y); (x-2,y); (x,y-1); (x,y-2)</cmath>. As a result, the way to count <math>\varphi (x,y)</math> is <cmath>\varphi (x,y)=\varphi (x-1,y)+\varphi (x-2,y)+\varphi (x,y-1)+\varphi (x,y-2)</cmath>
@@ Line 79: / Line 79: @@
 <cmath>\varphi (1,1)=\varphi (1,0)+\varphi (0,1)</cmath>
-Start with <math>\varphi (0,0)=1</math>, use this method, we can finally get <cmath>\varphi (4,4)=556</cmath>
+Start with <math>\varphi (0,0)=1</math>, use this method and draw the figure below, we can finally get <cmath>\varphi (4,4)=556</cmath>
+(In order to make the LaTeX thing more beautiful to look at, I put <math>0</math> to make every number a <math>3</math>-digits number)
+<cmath>005-020-071-207-\boxed{556}</cmath> <cmath>003-010-032-084-207</cmath> <cmath>002-005-014-032-071</cmath> <cmath>001-002-005-010-020</cmath> <cmath>001-001-002-003-005</cmath>
 So the total number of distinct sequences of jumps for the frog to reach <math>(4,4)</math> is <math>\boxed {556}</math>.
+~Solution by <math>BladeRunnerAUG</math> (Frank FYC)
 {{AIME box|year=2018|n=II|num-b=7|num-a=9}}
 {{MAA Notice}}

Page

Toolbox

Search