2014 AIME I Problem 11

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

Small hint:

Track

u = x + y

and

v = x - y:

each move changes each of

u

and

v

by

\pm 1,

independently and uniformly

Big hint:

The token ends on

|y| = |x|

when

u = 0

or

v = 0,

each with probability

\frac{\binom{6}{3}}{2^6};

add these and subtract the overlap

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

\frac{\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.