2003 AIME II Problem 13

Question

A bug starts at a vertex of an equilateral triangle. On each move, it randomly selects one of the two vertices where it is not currently located, and crawls along a side of the triangle to that vertex. Given that the probability that the bug moves to its starting vertex on its tenth move is

\frac{m}{n},

where

m

and

n

are relatively prime positive integers, find

m + n.

Answer

Answer: 683

Concepts:random walk recursive probability

Difficulty rating: 2650

Small hint:

Let

p_n

be the probability the bug is home after

n

moves; then

p_{n+1} = \frac{1}{2}(1 - p_n)

Big hint:

Subtract the fixed point:

p_n - \frac{1}{3}

is geometric with ratio

-\frac{1}{2}

Solution:

Let

p_n

be the probability that the bug is at its starting vertex after

n

moves, so

p_0 = 1.

The bug is home after move

n + 1

exactly when it was elsewhere after move

n

(probability

1 - p_n

) and then chose the starting vertex (probability

\frac{1}{2}

):

p_{n+1} = \frac{1}{2}(1 - p_n).

The fixed point of this recurrence is

\frac{1}{3},

and

p_{n+1} - \frac{1}{3} = -\frac{1}{2}\left(p_n - \frac{1}{3}\right),

so

p_n = \frac{1}{3} + \frac{2}{3}\left(-\frac{1}{2}\right)^n.

For

n = 10:

\begin{aligned} p_{10} &= \frac{1}{3}\left(1 + \frac{2}{1024}\right) \\ &= \frac{1}{3} \cdot \frac{1026}{1024} = \frac{171}{512}. \end{aligned}

Since

171 = 9 \cdot 19

and

512 = 2^9

share no factor,

m + n = 171 + 512 = 683.