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 "2019 AIME I Problems/Problem 5"
Line 18: Line 18:
 
==Solution 3==
 
==Solution 3==
  
−
Since the particle stops at one of the axes, we know that the particle most pass through (1,1). Thus, it suffices to consider the probability our particle will reach (1,1). Denote a move to the left, down, diagonally, as X,Y,Z, respectively. Then the only ways to get to (1,1) from (4,4) are the following:
+
Since the particle stops at one of the axes, we know that the particle most pass through <math>(1,1)</math>. Thus, it suffices to consider the probability our particle will reach <math>(1,1)</math>. Denote a move to the left, down, diagonally, as X,Y,Z, respectively. Then the only ways to get to <math>(1,1)</math> from <math>(4,4)</math> are the following:
  
−
(1) 0X 0Y 3Z  
+
(1) 0X 0Y 3Z \\
−
(2) 1X 1Y 2Z
+
(2) 1X 1Y 2Z \\
−
(3) 2X 2Y 1Z
+
(3) 2X 2Y 1Z \\
−
(4) 3X 3Y 0Z
+
(4) 3X 3Y 0Z \\
  
−
The probability of (1) is \frac{1}{3^3}. The probability of (2) is <math>\frac{\frac{4!}{2!}}{3^4} = \frac{12}{3^4}</math>. The probability of (3) is <math>\frac{\frac{5!}{2!2!}}{3^5} = \frac{30}{3^5}</math>. The probability of (4) is <math>\frac{\frac{6!}{3!3!}}{3^6} = \frac{20}{3^6}</math>. Adding all of these together, we obtain a total probability of <math>\frac{245}{3^6}</math> that our particle will hit (1,1). Trivially, there is a <math>\frac{1}{3}</math> chance our particle will hit (0,0) from (1,1). So our final probability will be <math>\frac{245}{3^6} \cdot \frac{1}{3} = </math>\frac{245}{3^7} \implies m = 245, n = 7 \implies \boxed{252}$
+
The probability of (1) is \frac{1}{3^3}. The probability of (2) is <math>\frac{\frac{4!}{2!}}{3^4} = \frac{12}{3^4}</math>. The probability of (3) is <math>\frac{\frac{5!}{2!2!}}{3^5} = \frac{30}{3^5}</math>. The probability of (4) is <math>\frac{\frac{6!}{3!3!}}{3^6} = \frac{20}{3^6}</math>. Adding all of these together, we obtain a total probability of <math>\frac{245}{3^6}</math> that our particle will hit (1,1). Trivially, there is a <math>\frac{1}{3}</math> chance our particle will hit (0,0) from (1,1). So our final probability will be <math>\frac{245}{3^6} \cdot \frac{1}{3} = \frac{245}{3^7} \implies m = 245, n = 7 \implies \boxed{252}</math>
  
 
~NotSoTrivial
 
~NotSoTrivial

Revision as of 12:44, 12 February 2021

Problem 5

A moving particle starts at the point $(4,4)$ and moves until it hits one of the coordinate axes for the first time. When the particle is at the point $(a,b)$, it moves at random to one of the points $(a-1,b)$, $(a,b-1)$, or $(a-1,b-1)$, each with probability $\frac{1}{3}$, independently of its previous moves. The probability that it will hit the coordinate axes at $(0,0)$ is $\frac{m}{3^n}$, where $m$ and $n$ are positive integers such that $m$ is not divisible by $3$. Find $m + n$.

Solution 1

One could recursively compute the probabilities of reaching $(0,0)$ as the first axes point from any point $(x,y)$ as \[P(x,y) = \frac{1}{3} P(x-1,y) + \frac{1}{3} P(x,y-1) + \frac{1}{3} P(x-1,y-1)\] for $x,y \geq 1,$ and the base cases are $P(0,0) = 1, P(x,0) = P(y,0) = 0$ for any $x,y$ not equal to zero. We then recursively find $P(4,4) = \frac{245}{2187}$ so the answer is $245 + 7 = \boxed{252}$.


If this algebra seems intimidating, you can watch a nice pictorial explanation of this by On The Spot Stem. https://www.youtube.com/watch?v=XBRuy3_TM9w

Solution 2

Obviously, the only way to reach (0,0) is to get to (1,1) and then have a $\frac{1}{3}$ chance to get to (0,0). Let x denote a move left 1 unit, y denote a move down 1 unit, and z denote a move left and down one unit each. The possible cases for these moves are $(x,y,z)=(0,0,3),(1,1,2),(2,2,1)$ and $(3,3,0)$. This gives a probability of $1 \cdot \frac{1}{27} + \frac{4!}{2!} \cdot \frac{1}{81} + \frac{5!}{2! \cdot 2!} \cdot \frac{1}{243} +\frac{6!}{3! \cdot 3!} \cdot \frac{1}{729}=\frac{245}{729}$ to get to $(1,1)$. The probability of reaching $(0,0)$ is $\frac{245}{3^7}$. This gives $245+7=\boxed{252}$.

Solution 3

Since the particle stops at one of the axes, we know that the particle most pass through $(1,1)$. Thus, it suffices to consider the probability our particle will reach $(1,1)$. Denote a move to the left, down, diagonally, as X,Y,Z, respectively. Then the only ways to get to $(1,1)$ from $(4,4)$ are the following:

(1) 0X 0Y 3Z \\ (2) 1X 1Y 2Z \\ (3) 2X 2Y 1Z \\ (4) 3X 3Y 0Z \\

The probability of (1) is \frac{1}{3^3}. The probability of (2) is $\frac{\frac{4!}{2!}}{3^4} = \frac{12}{3^4}$. The probability of (3) is $\frac{\frac{5!}{2!2!}}{3^5} = \frac{30}{3^5}$. The probability of (4) is $\frac{\frac{6!}{3!3!}}{3^6} = \frac{20}{3^6}$. Adding all of these together, we obtain a total probability of $\frac{245}{3^6}$ that our particle will hit (1,1). Trivially, there is a $\frac{1}{3}$ chance our particle will hit (0,0) from (1,1). So our final probability will be $\frac{245}{3^6} \cdot \frac{1}{3} = \frac{245}{3^7} \implies m = 245, n = 7 \implies \boxed{252}$

~NotSoTrivial

Video Solution

Unique solution: https://youtu.be/I-8xZGhoDUY

~Shreyas S

See Also

2019 AIME I (Problems • Answer Key • Resources)
Preceded by
Problem 4 		Followed by
Problem 6
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=2019_AIME_I_Problems/Problem_5&oldid=146090"