1995 AIME Problems/Problem 3
From AoPSWiki
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
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 
.
See also
| 1995 AIME (Problems • Resources) | ||
| Preceded by Problem 2 | Followed by Problem 4 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
