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

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:$ $p_{10} = \frac{1}{3}\left(1 + \frac{2}{1024}\right) = \frac{1}{3} \cdot \frac{1026}{1024} = \frac{171}{512}.$ Since $171 = 9 \cdot 19$ and $512 = 2^9$ share no factor, $m + n = 171 + 512 = 683.$

2003 AIME II Problem 13

Solution:

Problem 13 in Other Years