1995 AIME Problems/Problem 3
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
First 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 ways for the object to end at 2,2. To go a permutation of R,R,R,U,U,L or 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.
But, the object can also get to 2,2, then move away. That is also a possible way the object can move. 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 ways were already counted in the first case, so we should only count 12 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.