Difference between revisions of "2018 AIME II Problems/Problem 8"
(→Solution 1) |
(→Solution 2) |
||
Line 64: | Line 64: | ||
Adding up all these cases gives us <math>70+210+180+30+60+6=\boxed{556}</math> ways. | Adding up all these cases gives us <math>70+210+180+30+60+6=\boxed{556}</math> ways. | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | 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> | ||
+ | |||
+ | Also, for special cases, <cmath>\varphi (0,y)=\varphi (0,y-1)+\varphi (0,y-2)</cmath> | ||
+ | |||
+ | <cmath>\varphi (x,0)=\varphi (x-1,0)+\varphi (x-2,0)</cmath> | ||
+ | |||
+ | <cmath>\varphi (x,1)=\varphi (x-1,1)+\varphi (x-2,1)+\varphi (x,0)</cmath> | ||
+ | |||
+ | <cmath>\varphi (1,y)=\varphi (1,y-1)+\varphi (1,y-2)+\varphi (0,y)</cmath> | ||
+ | |||
+ | <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> | ||
+ | |||
+ | So the total number of distinct sequences of jumps for the frog to reach <math>(4,4)</math> is <math>\boxed {556}</math>. | ||
{{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 20:13, 6 October 2018
Contents
[hide]Problem
A frog is positioned at the origin of the coordinate plane. From the point , the frog can jump to any of the points , , , or . Find the number of distinct sequences of jumps in which the frog begins at and ends at .
Solution 1
We solve this problem by working backwards. Notice, the only points the frog can be on to jump to in one move are and . This applies to any other point, thus we can work our way from to , recording down the number of ways to get to each point recursively.
, , ,
A diagram of the numbers:
5 - 20 - 71 - 207 -
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 , , , and as , , , and , respectively. Then the possible sequences of moves that will take the frog from to are all the permutations of , , , , , , , , and . We can reduce the number of cases using symmetry.
Case 1:
There are possibilities for this case.
Case 2: or
There are possibilities for this case.
Case 3:
There are possibilities for this case.
Case 4: or
There are possibilities for this case.
Case 5: or
There are possibilities for this case.
Case 6:
There are possibilities for this case.
Adding up all these cases gives us ways.
Solution 3
Mark the total number of distinct sequences of jumps for the frog to reach the point as . Consider for each point in the first quadrant, there are only possible points in the first quadrant for frog to reach point , and these 4 points are . As a result, the way to count is
Also, for special cases,
Start with , use this method, we can finally get
So the total number of distinct sequences of jumps for the frog to reach is .
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.