, 2020

Solution:
The key idea is to consider $(a+b, a-b)$, where $(a, b)$ is where Anastasia walks on. Then, the first and second coordinates are independent random walks starting at $1$, and we want to find the probability that the first is divisible by $3$ when the second reaches $0$ for the first time. Let $C_{n}$ be the $n$th Catalan number. The probability that the second random walk first reaches $0$ after $2n-1$ steps is
$$\frac{C_{n-1}}{2^{2n-1}},$$
and the probability that the first is divisible by $3$ after $2n-1$ steps is
$$\frac{1}{2^{2n-1}} \sum_{i \equiv n \bmod 3} \binom{2n-1}{i}$$
(by letting $i$ be the number of $-1$ steps). We then need to compute
$$\sum_{n=1}^{\infty} \left( \frac{C_{n-1}}{4^{2n-1}} \sum_{i \equiv n \bmod 3} \binom{2n-1}{i} \right).$$
By a standard root of unity filter,
$$\sum_{i \equiv n \bmod 3} \binom{2n-1}{i} = \frac{4^{n} + 2}{6}.$$
Letting
$$P(x) = \frac{2}{1 + \sqrt{1-4x}} = \sum_{n=0}^{\infty} C_{n} x^{n}$$
be the generating function for the Catalan numbers, we find that the answer is
$$\frac{1}{6} P\left(\frac{1}{4}\right) + \frac{1}{12} P\left(\frac{1}{16}\right) = \frac{1}{3} + \frac{1}{12} \cdot \frac{2}{1 + \sqrt{\frac{3}{4}}} = \frac{3-\sqrt{3}}{3}.$$