1995 AIME Problems/Problem 3

Problem

Starting at $(0,0),$ 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 $p$ be the probability that the object reaches $(2,2)$ in six or fewer steps. Given that $p$ can be written in the form $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$

Solution

It takes an even number of steps for the object to reach $(2,2)$ , so the number of steps the object may have taken is either $4$ or $6$ .

If the object took $4$ steps, then it must have gone two steps N and two steps E, in some permutation. There are $\frac{4!}{2!2!} = 6$ ways for these four steps of occuring, and the probability is $\frac{6}{4^{4}}$ .

If the object took $6$ 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 $\frac{6!}{3!2!1!} = 60$ 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 $(2,2)$ in four moves. There are $\frac{4!}{2!2!}$ ways to order those four steps and $2!$ ways to determine the order of the remaining two steps, for a total of $12$ sequences that we have to exclude. This gives $60-12=48$ sequences of steps. There are the same number of sequences for the steps N,N,E,E,E,W, so the probability here is $\frac{2 \times 48}{4^6}$ .

The total probability is $\frac{6}{4^4} + \frac{96}{4^6} = \frac{3}{64}$ , and $m+n= \boxed{067}$ .

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

Page

Toolbox

Search

1995 AIME Problems/Problem 3

Problem

Solution

See also