Question

A token starts at the point $(0, 0)$ of an $xy$ -coordinate grid and then makes a sequence of six moves. Each move is $1$ unit in a direction parallel to one of the coordinate axes. Each move is selected randomly from the four possible directions and independently of the other moves. The probability that the token ends at a point on the graph of $|y| = |x|$ is $\frac{m}{n},$ where $m$ and $n$ are relatively prime positive integers. Find $m + n.$

Answer

Answer: 391

Concepts:random walk independent events inclusion-exclusion

Difficulty rating: 2990

Solution:

Work in the diagonal coordinates $u = x + y$ and $v = x - y.$ Each of the four moves changes $u$ by $\pm 1$ and $v$ by $\pm 1,$ and the four moves realize all four sign combinations equally often — so $u$ and $v$ perform independent six-step $\pm 1$ walks. The token ends on $|y| = |x|$ exactly when $y = \pm x,$ that is, when $u = 0$ or $v = 0.$

Each of $u = 0$ and $v = 0$ requires three $+1$ s and three $-1$ s, with probability $\binom{6}{3}/2^6 = \frac{20}{64} = \frac{5}{16}.$ By independence and inclusion-exclusion, the probability is $\begin{aligned} &\frac{5}{16} + \frac{5}{16} - \left(\frac{5}{16}\right)^2 \\ &= \frac{160 - 25}{256} = \frac{135}{256}. \end{aligned}$

Thus $m + n = 135 + 256 = 391.$

2014 AIME I Problem 11

Answer: 391

Difficulty rating: 2990

Solution:

Problem 11 in Other Years