, 2018

Solution:

We make the following claim: In a game with $n \times m$ grid where $n \leq m$ and $n \equiv m \pmod{2}$, the probability that Sarah wins is $\frac{1}{2^{n}}$ under optimal play.

Proof: We induct on $n$. First consider the base case $n=0$. In this case Rachel is confined on a line, so Sarah is guaranteed to win.

We then consider the case where $n=m$ (a square grid). If Rachel and Sarah move in parallel directions at first, then Rachel can win if she keeps moving in this direction, since Sarah will not be able to catch Rachel no matter what. Otherwise, the problem is reduced to a $(n-1) \times (n-1)$ grid. Therefore, the optimal strategy for both players is to choose a direction completely randomly, since any bias can be abused by the other player. So the reduction happens with probability $\frac{1}{2}$, and by induction hypothesis Sarah will win with probability $\frac{1}{2^{n-1}}$, so on a $n \times n$ grid Sarah wins with probability $\frac{1}{2^{n}}$.

Now we use induction to show that when $n < m$, both players will move in the longer ($m$) direction until they are at corners of a square grid (in which case Sarah wins with probability $\frac{1}{2^{n}}$). If Sarah moves in the $n$ direction and Rachel moves in the $m$ (or $n$) direction, then Rachel can just move in the $n$ direction until she reaches the other side of the grid and Sarah will not be able to catch her. If Rachel moves in the $n$ direction and Sarah moves in the $m$ direction, then the problem is reduced to a $(n-1) \times (m-1)$ grid, which means that Sarah's winning probability is now doubled to $\frac{1}{2^{n-1}}$ by induction hypothesis. Therefore it is suboptimal for either player to move in the shorter ($n$) direction. This shows that the game will be reduced to $n \times n$ with optimal play, and thus the claim is proved.

From the claim, we can conclude that the probability that Rachel wins is $1 - \frac{1}{2^{6}} = \frac{63}{64}$.