Difference between revisions of "1995 AIME Problems/Problem 3"
Alexlikemath (talk | contribs) (→Solution) |
Alexlikemath (talk | contribs) m (→Solution 2) |
||
Line 15: | Line 15: | ||
Let's let the object wander for 6 steps so we get a constant denominator of <math>4^{6}</math> | Let's let the object wander for 6 steps so we get a constant denominator of <math>4^{6}</math> | ||
− | + | In the first case, we count how many ways the object can end at (2,2), at the end of 6 steps. We will also count it even if we go to (2,2), and go back to (2,2). So, there are 2 different paths for the object to end at (2,2): | |
− | + | 1.To go a permutation of R,R,R,U,U,L or | |
− | So, in all, there are 120+72 ways for the object to achieve it's goal of moving to 2,2. Put that over our denominator, we get <math>\frac{192}{4^{6}} = \frac{3}{4^{3}} = \frac{3}{64}</math>, in which adding the numerator and denominator get us an answer of <math>\boxed{067}</math> | + | 2.To go a permutation of R,R,U,U,U,D. |
+ | |||
+ | There are 60 ways to permute for each case, giving a total of 120 ways for the object to succeed and end at (2,2). In these 120 ways the object could reach (2,2) first and then come back to (2,2). This will be a factor in our second case. | ||
+ | |||
+ | In the second case, the object can get to (2,2) first in 4 moves, then move away from (2,2) with the remaing 2 moves. So, there are 6 ways to get to (2,2) in 4 moves, then there are 16 ways the object can "move around", but 4 of the ways will return the object back to (2,2). Those 4 ways were already counted in the first case, so we should only count 12 of the 16 ways to prevent over-counting. Thus, there are <math>12*6 = </math> 72 ways in the second case. | ||
+ | |||
+ | So, in all, there are 120+72 ways for the object to achieve it's goal of moving to (2,2). Put that over our denominator, we get <math>\frac{192}{4^{6}} = \frac{3}{4^{3}} = \frac{3}{64}</math>, in which adding the numerator and denominator get us an answer of <math>\boxed{067}</math> | ||
Latest revision as of 23:15, 16 June 2019
Contents
Problem
Starting at an object moves in the coordinate plane via a sequence of steps, each of length one. Each step is left, right, up, or down, all four equally likely. Let
be the probability that the object reaches
in six or fewer steps. Given that
can be written in the form
where
and
are relatively prime positive integers, find
Solution 1
It takes an even number of steps for the object to reach , so the number of steps the object may have taken is either
or
.
If the object took steps, then it must have gone two steps N and two steps E, in some permutation. There are
ways for these four steps of occuring, and the probability is
.
If the object took steps, then it must have gone two steps N and two steps E, and an additional pair of moves that would cancel out, either N/S or W/E. The sequences N,N,N,E,E,S can be permuted in
ways. However, if the first four steps of the sequence are N,N,E,E in some permutation, it would have already reached the point
in four moves. There are
ways to order those four steps and
ways to determine the order of the remaining two steps, for a total of
sequences that we have to exclude. This gives
sequences of steps. There are the same number of sequences for the steps N,N,E,E,E,W, so the probability here is
.
The total probability is , and
.
Solution 2
Let's let the object wander for 6 steps so we get a constant denominator of
In the first case, we count how many ways the object can end at (2,2), at the end of 6 steps. We will also count it even if we go to (2,2), and go back to (2,2). So, there are 2 different paths for the object to end at (2,2):
1.To go a permutation of R,R,R,U,U,L or
2.To go a permutation of R,R,U,U,U,D.
There are 60 ways to permute for each case, giving a total of 120 ways for the object to succeed and end at (2,2). In these 120 ways the object could reach (2,2) first and then come back to (2,2). This will be a factor in our second case.
In the second case, the object can get to (2,2) first in 4 moves, then move away from (2,2) with the remaing 2 moves. So, there are 6 ways to get to (2,2) in 4 moves, then there are 16 ways the object can "move around", but 4 of the ways will return the object back to (2,2). Those 4 ways were already counted in the first case, so we should only count 12 of the 16 ways to prevent over-counting. Thus, there are 72 ways in the second case.
So, in all, there are 120+72 ways for the object to achieve it's goal of moving to (2,2). Put that over our denominator, we get , in which adding the numerator and denominator get us an answer of
- AlexLikeMath
See also
1995 AIME (Problems • Answer Key • Resources) | ||
Preceded by Problem 2 |
Followed by Problem 4 | |
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.