1995 AIME Problems/Problem 3
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
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 .
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
|1995 AIME (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|