Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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

(→‎Solution)
m
 
(21 intermediate revisions by 11 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 recursively.  
 
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>(0,0): 1</math>
 
<math>(0,0): 1</math>
 +
 
<math>(1,0)=(0,1)=1</math>
 
<math>(1,0)=(0,1)=1</math>
 +
 
<math>(2,0)=(0, 2)=2</math>
 
<math>(2,0)=(0, 2)=2</math>
 +
 
<math>(3,0)=(0, 3)=3</math>
 
<math>(3,0)=(0, 3)=3</math>
 +
 
<math>(4,0)=(0, 4)=5</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>(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>(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>(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>
 
<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

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:

[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 $(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 $3$ digits)

\[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)

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) $\dbinom{8}{4} = 70$ ways total

x-distribution: 1-1-1-1 (1 way to order) y-distribution: 1-1-2 (3 ways to order) $\dbinom{7}{3} \times 3= 105$ ways total

x-distribution: 1-1-1-1 (1 way to order) y-distribution: 2-2 (1 way to order) $\dbinom{6}{4} = 15$ ways total

x-distribution: 1-1-2 (3 ways to order) y-distribution: 1-1-1-1 (1 way to order) $\dbinom{7}{3} \times 3= 105$ ways total

x-distribution: 1-1-2 (3 ways to order) y-distribution: 1-1-2 (3 ways to order) $\dbinom{6}{3} \times 9= 180$ ways total

x-distribution: 1-1-2 (3 ways to order) y-distribution: 2-2 (1 way to order) $\dbinom{5}{3} \times 3 = 30$ ways total

x-distribution: 2-2 (1 way to order) y-distribution: 1-1-1-1 (1 way to order) $\dbinom{6}{4} = 15$ ways total

x-distribution: 2-2 (1 way to order) y-distribution: 1-1-2 (3 ways to order) $\dbinom{5}{3} \times 3 = 30$ ways total

x-distribution: 2-2 (1 way to order) y-distribution: 2-2 (1 way to order) $\dbinom{4}{2} = 6$ ways total

$6+30+15+105+180+70+30+15+105=\boxed{556}$ -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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_II_Problems/Problem_8&oldid=188082"