Difference between revisions of "2018 AIME II Problems/Problem 8"
(→Problem) |
m |
||
(22 intermediate revisions by 12 users not shown) | |||
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. | + | 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>\ | + | |
− | \ | + | <math>(0,0): 1</math> |
− | \ | + | |
+ | <math>(1,0)=(0,1)=1</math> | ||
+ | |||
+ | <math>(2,0)=(0, 2)=2</math> | ||
+ | |||
+ | <math>(3,0)=(0, 3)=3</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>(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>(4,4)=2\cdot \left( (4,2)+(4,3)\right) = 2\cdot \left( 207+71\right)=2\cdot 278=\boxed{556}</math> | ||
+ | |||
+ | A diagram of the numbers: | ||
+ | |||
+ | <asy> | ||
+ | import graph; | ||
+ | add(shift(0,0)*grid(4,4)); | ||
+ | label((0,0), "1", SW); | ||
+ | label((1,0), "1", SW); | ||
+ | label((2,0), "2", SW); | ||
+ | label((3,0), "3", SW); | ||
+ | label((4,0), "5", SW); | ||
+ | |||
+ | label((0,1), "1", SW); | ||
+ | label((1,1), "2", SW); | ||
+ | label((2,1), "5", SW); | ||
+ | label((3,1), "10", SW); | ||
+ | label((4,1), "20", SW); | ||
+ | |||
+ | label((0,2), "2", SW); | ||
+ | label((1,2), "5", SW); | ||
+ | label((2,2), "14", SW); | ||
+ | label((3,2), "32", SW); | ||
+ | label((4,2), "71", SW); | ||
+ | |||
+ | label((0,3), "3", SW); | ||
+ | label((1,3), "10", SW); | ||
+ | label((2,3), "32", SW); | ||
+ | label((3,3), "84", SW); | ||
+ | label((4,3), "207", SW); | ||
+ | |||
+ | label((0,4), "5", SW); | ||
+ | label((1,4), "20", SW); | ||
+ | label((2,4), "71", SW); | ||
+ | label((3,4), "207", SW); | ||
+ | label((4,4), "556", SW); | ||
+ | </asy> | ||
+ | |||
+ | ~First | ||
+ | |||
+ | ==Solution 2== | ||
+ | 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> | ||
+ | |||
+ | 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. | ||
+ | |||
+ | ==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 <math>4</math> 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 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 <math>3</math> digits) | ||
+ | |||
+ | <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) | ||
+ | |||
+ | ==Solution 4 (Casework)== | ||
+ | |||
+ | Casework Solution: | ||
+ | x-distribution: 1-1-1-1 (1 way to order) | ||
+ | y-distribution: 1-1-1-1 (1 way to order) | ||
+ | <math>\dbinom{8}{4} = 70</math> ways total | ||
+ | |||
+ | x-distribution: 1-1-1-1 (1 way to order) | ||
+ | y-distribution: 1-1-2 (3 ways to order) | ||
+ | <math>\dbinom{7}{3} \times 3= 105</math> ways total | ||
+ | |||
+ | x-distribution: 1-1-1-1 (1 way to order) | ||
+ | y-distribution: 2-2 (1 way to order) | ||
+ | <math>\dbinom{6}{4} = 15</math> ways total | ||
+ | |||
+ | x-distribution: 1-1-2 (3 ways to order) | ||
+ | y-distribution: 1-1-1-1 (1 way to order) | ||
+ | <math>\dbinom{7}{3} \times 3= 105</math> ways total | ||
+ | |||
+ | x-distribution: 1-1-2 (3 ways to order) | ||
+ | y-distribution: 1-1-2 (3 ways to order) | ||
+ | <math>\dbinom{6}{3} \times 9= 180</math> ways total | ||
+ | |||
+ | x-distribution: 1-1-2 (3 ways to order) | ||
+ | y-distribution: 2-2 (1 way to order) | ||
+ | <math>\dbinom{5}{3} \times 3 = 30</math> ways total | ||
+ | |||
+ | x-distribution: 2-2 (1 way to order) | ||
+ | y-distribution: 1-1-1-1 (1 way to order) | ||
+ | <math>\dbinom{6}{4} = 15</math> ways total | ||
+ | |||
+ | x-distribution: 2-2 (1 way to order) | ||
+ | y-distribution: 1-1-2 (3 ways to order) | ||
+ | <math>\dbinom{5}{3} \times 3 = 30</math> ways total | ||
+ | |||
+ | x-distribution: 2-2 (1 way to order) | ||
+ | y-distribution: 2-2 (1 way to order) | ||
+ | <math>\dbinom{4}{2} = 6</math> ways total | ||
+ | |||
+ | <math>6+30+15+105+180+70+30+15+105=\boxed{556}</math> | ||
+ | -fidgetboss_4000 | ||
+ | |||
+ | ==Video Solution== | ||
+ | |||
+ | On The Spot STEM : | ||
+ | https://www.youtube.com/watch?v=v2fo3CaAhmM | ||
+ | |||
+ | ==See Also== | ||
{{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}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] |
Latest revision as of 16:43, 26 January 2023
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:
~First
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 (General Case)
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 points are . As a result, the way to count is
Also, for special cases,
Start with , use this method and draw the figure below, we can finally get (In order to make the LaTeX thing more beautiful to look at, I put to make every number digits)
So the total number of distinct sequences of jumps for the frog to reach is .
~Solution by (Frank FYC)
Solution 4 (Casework)
Casework Solution: x-distribution: 1-1-1-1 (1 way to order) y-distribution: 1-1-1-1 (1 way to order) ways total
x-distribution: 1-1-1-1 (1 way to order) y-distribution: 1-1-2 (3 ways to order) ways total
x-distribution: 1-1-1-1 (1 way to order) y-distribution: 2-2 (1 way to order) ways total
x-distribution: 1-1-2 (3 ways to order) y-distribution: 1-1-1-1 (1 way to order) ways total
x-distribution: 1-1-2 (3 ways to order) y-distribution: 1-1-2 (3 ways to order) ways total
x-distribution: 1-1-2 (3 ways to order) y-distribution: 2-2 (1 way to order) ways total
x-distribution: 2-2 (1 way to order) y-distribution: 1-1-1-1 (1 way to order) ways total
x-distribution: 2-2 (1 way to order) y-distribution: 1-1-2 (3 ways to order) ways total
x-distribution: 2-2 (1 way to order) y-distribution: 2-2 (1 way to order) ways total
-fidgetboss_4000
Video Solution
On The Spot STEM : https://www.youtube.com/watch?v=v2fo3CaAhmM
See Also
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.