Difference between revisions of "2018 AIME II Problems/Problem 8"
(→Solution 3 (General Case)) |
m |
||
(11 intermediate revisions by 7 users not shown) | |||
Line 26: | Line 26: | ||
A diagram of the numbers: | 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); | ||
− | 3 | + | 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); | ||
− | 2 | + | 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); | ||
− | 1 | + | 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); | ||
− | 1 | + | 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== | ==Solution 2== | ||
Line 79: | Line 105: | ||
<cmath>\varphi (1,1)=\varphi (1,0)+\varphi (0,1)</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 | + | 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> | <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> | ||
Line 87: | Line 113: | ||
~Solution by <math>BladeRunnerAUG</math> (Frank FYC) | ~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 17:43, 26 January 2023
Contents
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.