Question

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 $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$

Answer

Answer: 67

Concepts:random walk basic counting complementary probability

Difficulty rating: 1850

Small Hint:

The target can first be reached only after $4$ or $6$ steps

Big Hint:

From the six-step paths ending at the target, subtract those that already arrived at step $4$

Solution:

There are $\binom42=6$ four-step paths to $(2,2).$ There are $60+60=120$ six-step paths ending there: the extra opposite pair is either left-right or down-up. Of these, $6\cdot4=24$ first reach the target at step $4$ and then make a two-step return. Therefore $p=\frac6{4^4}+\frac{120-24}{4^6}=\frac3{64}.$ Thus $m+n=3+64=67.$

1995 AIME Problem 3

Answer: 67

Difficulty rating: 1850

Small Hint:

Big Hint:

Solution:

Problem 3 in Other Years