Difference between revisions of "2019 AIME I Problems/Problem 5"
(45 intermediate revisions by 24 users not shown) | |||
Line 1: | Line 1: | ||
− | The | + | ==Problem== |
+ | A moving particle starts at the point <math>(4,4)</math> and moves until it hits one of the coordinate axes for the first time. When the particle is at the point <math>(a,b)</math>, it moves at random to one of the points <math>(a-1,b)</math>, <math>(a,b-1)</math>, or <math>(a-1,b-1)</math>, each with probability <math>\frac{1}{3}</math>, independently of its previous moves. The probability that it will hit the coordinate axes at <math>(0,0)</math> is <math>\frac{m}{3^n}</math>, where <math>m</math> and <math>n</math> are positive integers such that <math>m</math> is not divisible by <math>3</math>. Find <math>m + n</math>. | ||
+ | |||
+ | ==Solution 1== | ||
+ | One could recursively compute the probabilities of reaching <math>(0,0)</math> as the first axes point from any point <math>(x,y)</math> as <cmath>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)</cmath> for <math>x,y \geq 1,</math> and the base cases are | ||
+ | <math>P(0,0) = 1, P(x,0) = P(y,0) = 0</math> for any <math>x,y</math> not equal to zero. | ||
+ | We then recursively find <math>P(4,4) = \frac{245}{2187}</math> so the answer is <math>245 + 7 = \boxed{252}</math>. | ||
+ | |||
+ | |||
+ | |||
+ | 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 <math>\frac{1}{3}</math> 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 <math>(x,y,z)=(0,0,3),(1,1,2),(2,2,1)</math> and <math>(3,3,0)</math>. This gives a probability of <math>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}</math> to get to <math>(1,1)</math>. The probability of reaching <math>(0,0)</math> is <math>\frac{245}{3^7}</math>. This gives <math>245+7=\boxed{252}</math>. | ||
+ | |||
+ | ==Solution 3== | ||
+ | |||
+ | 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>. Then the only ways to get to <math>(1,1)</math> from <math>(4,4)</math> are the following: | ||
+ | |||
+ | (1) 3 moves diagonally | ||
+ | |||
+ | (2) 2 moves diagonally, 1 move left, 1 move down | ||
+ | |||
+ | (3) 1 move diagonally, 2 moves left and 2 moves down. | ||
+ | |||
+ | (4) 3 moves left, 3 moves down. | ||
+ | |||
+ | The probability of (1) is <math>\frac{1}{3^3}</math>. 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 <math>(1,1)</math>. Trivially, there is a <math>\frac{1}{3}</math> chance our particle will hit <math>(0,0)</math> from <math>(1,1)</math>. 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 | ||
+ | ==Solution 4 (Official MAA)== | ||
+ | All paths that first hit the axes at the origin must pass through the point <math>(1,1)</math>. There are <math>63</math> paths from the point <math>(4,4)</math> to the point <math>(1,1)</math>: <math>\tbinom{6}{3}=20</math> that take <math>3</math> steps left and <math>3</math> steps down, <math>\tbinom{5}{2\,2\,1}=30</math> that take <math>2</math> steps left, <math>2</math> steps down, and <math>1</math> diagonal step, <math>\tbinom{4}{1\,1\,2}=12</math> steps that take <math>1</math> step left, <math>1</math> steps down, and <math>2</math> diagonal steps, and <math>1</math> that takes <math>3</math> diagonal steps. The total probability of moving from <math>(4,4)</math> to <math>(1,1)</math> is therefore <cmath>\frac{1}{3^6}\cdot20+\frac{1}{3^5}\cdot30+\frac{1}{3^4}\cdot12+\frac{1}{3^3}\cdot1=\frac{245}{3^6}.</cmath> Multiplying by <math>\tfrac13</math> gives <math>\tfrac{245}{3^7},</math> the probability that the path first reaches the axes at the origin. The requested sum is <math>245+7=252</math>. | ||
+ | ==Video Solution #1(A nice visual explanation)== | ||
+ | https://youtu.be/JQdad7APQG8?t=1340 | ||
+ | |||
+ | ==Video Solution== | ||
+ | Unique solution: https://youtu.be/I-8xZGhoDUY | ||
+ | |||
+ | ~Shreyas S | ||
− | |||
− | |||
==See Also== | ==See Also== | ||
{{AIME box|year=2019|n=I|num-b=4|num-a=6}} | {{AIME box|year=2019|n=I|num-b=4|num-a=6}} | ||
+ | |||
+ | [[Category:Intermediate Probability Problems]] | ||
{{MAA Notice}} | {{MAA Notice}} |
Latest revision as of 15:51, 25 February 2021
Contents
Problem
A moving particle starts at the point and moves until it hits one of the coordinate axes for the first time. When the particle is at the point
, it moves at random to one of the points
,
, or
, each with probability
, independently of its previous moves. The probability that it will hit the coordinate axes at
is
, where
and
are positive integers such that
is not divisible by
. Find
.
Solution 1
One could recursively compute the probabilities of reaching as the first axes point from any point
as
for
and the base cases are
for any
not equal to zero.
We then recursively find
so the answer is
.
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 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
and
. This gives a probability of
to get to
. The probability of reaching
is
. This gives
.
Solution 3
Since the particle stops at one of the axes, we know that the particle most pass through . Thus, it suffices to consider the probability our particle will reach
. Then the only ways to get to
from
are the following:
(1) 3 moves diagonally
(2) 2 moves diagonally, 1 move left, 1 move down
(3) 1 move diagonally, 2 moves left and 2 moves down.
(4) 3 moves left, 3 moves down.
The probability of (1) is . The probability of (2) is
. The probability of (3) is
. The probability of (4) is
. Adding all of these together, we obtain a total probability of
that our particle will hit
. Trivially, there is a
chance our particle will hit
from
. So our final probability will be
~NotSoTrivial
Solution 4 (Official MAA)
All paths that first hit the axes at the origin must pass through the point . There are
paths from the point
to the point
:
that take
steps left and
steps down,
that take
steps left,
steps down, and
diagonal step,
steps that take
step left,
steps down, and
diagonal steps, and
that takes
diagonal steps. The total probability of moving from
to
is therefore
Multiplying by
gives
the probability that the path first reaches the axes at the origin. The requested sum is
.
Video Solution #1(A nice visual explanation)
https://youtu.be/JQdad7APQG8?t=1340
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.