, 2013

Solution:

Answer: $\quad \frac{2}{3}+\frac{1}{3}\left(\frac{1}{4}\right)^{2013}$ OR $\frac{2^{4027}+1}{3 \cdot 2^{4026}}$ OR $\frac{2}{3}+\frac{1}{3}\left(\frac{1}{2}\right)^{4026}$ OR $\frac{2}{3}+\frac{1}{3}\left(\frac{1}{64}\right)^{671}$

Label the runners $A$ and $B$ and arbitrarily fix an orientation of the hexagon. Let $p_{t}(i)$ be the probability that $A$ is $i(\bmod 6)$ vertices to the right of $B$ at time $t$, so without loss of generality $p_{0}(1)=1$ and $p_{0}(2)=\cdots=p_{0}(6)=0$. Then for $t>0$, $p_{t}(i)=\frac{1}{4} p_{t-1}(i-2)+\frac{1}{2} p_{t-1}(i)+\frac{1}{4} p_{t-1}(i+2)$.

In particular, $p_{t}(2)=p_{t}(4)=p_{t}(6)=0$ for all $t$, so we may restrict our attention to $p_{t}(1), p_{t}(3), p_{t}(5)$. Thus $p_{t}(1)+p_{t}(3)+p_{t}(5)=1$ for all $t \geq 0$, and we deduce $p_{t}(i)=\frac{1}{4}+\frac{1}{4} p_{t-1}(i)$ for $i=1,3,5$.

Finally, let $f(t)=p_{t}(1)+p_{t}(5)$ denote the probability that $A, B$ are 1 vertex apart at time $t$, so $f(t)=\frac{1}{2}+\frac{1}{4} f(t-1) \Longrightarrow f(t)-\frac{2}{3}=\frac{1}{4}\left[f(t-1)-\frac{2}{3}\right]$, and we conclude that $f(2013)=\frac{2}{3}+\frac{1}{3}\left(\frac{1}{4}\right)^{2013}$.