HMMT-Feb 2018 comb, Problem 6

Sarah stands at $(0,0)$ and Rachel stands at $(6,8)$ in the Euclidean plane. Sarah can only move 1 unit in the positive $x$ or $y$ direction, and Rachel can only move 1 unit in the negative $x$ or $y$ direction. Each second, Sarah and Rachel see each other, independently pick a direction to move at the same time, and move to their new position. Sarah catches Rachel if Sarah and Rachel are ever at the same point. Rachel wins if she is able to get to $(0,0)$ without being caught; otherwise, Sarah wins. Given that both of them play optimally to maximize their probability of winning, what is the probability that Rachel wins?

Solution: We make the following claim: In a game with $n \times m$ grid where $n \leq m$ and $n \equiv m(\bmod 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 keep 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 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 player 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}$. $\fbox{\frac{63}{64}}$.

Answer: \frac{63}{64}