Chip and Dale play on a $100 \times 100$ table. In the beginning, a chess king stands in the upper left corner of the table. At each move the king is moved one square right, down or right-down diagonally. A player cannot move in the direction used by his opponent in the previous move. The players move in turn, Chip begins. The player that cannot move loses. Which player has a winning strategy?
Problem
Source: 2024 Tuymaada Senior P2
Tags: combinatorics, game, Game Theory, Combinatorial games, Tuymaada
Seicchi28
09.07.2024 23:04
Let's give each cell coordinates $(x, y) \coloneq (a, b)$ if it's located on the $b$-th row from the bottom and $a$-th column from the right, where the coordinate starts from $0$ (so the bottom right corner of the table has coordinate $(0, 0)$, going leftward increases the $x$ coordinate by $1$, and going upward increases the $y$ coordinate by $1$). We claim that the first player loses if the game starts from the cell with coordinate $(a, b)$ where $a + b \equiv 0 \pmod 3$ and $1/2 \le a/b \le 2$ $(\star)$. Since the upper left corner has coordinate $(99, 99)$, the first player loses. We will describe the winning strategy of the $\boxed{\text{second player}}$.
Assume it is the first player's turn now. Assume the chess king is on the coordinate $(p, q)$ where $p + q \equiv 0 \pmod 3$ and $1/2 < p/q < 2$, i.e. $p = a+k, q = 2a-k$ for some $1 \le k \le a-1$. If the chess king moves right or down, then the second player moves it right-down on the next turn (and vice-versa), so the coordinate of the king now is $(p - 2, q - 1) = (a+k-2, 2a-k-1)$ or $(p - 1, q - 2)=(a+k-1, 2a-k-2)$, which still satisfies $(\star)$. Now, assume the chess king is on the coordinate $(p, q)$ where $p + q \equiv 0 \pmod 3$ and $p/q = 1/2$ or $2$. WLOG $p = 2k$ and $q = k$ for some positive integer $k$. If the chess king moves right, then the second player moves it right-down on the next turn, so the coordinate is now $(2k-2, k-1)$, and we repeat the strategy for $k \coloneq k - 1$. Otherwise, the chess king moves down or right-down, and after that the second player moves the king rightward (to $(2k-2, k-1)$ or $(2k-1, k-2)$, depending on the first player's turn), and also forcing the succeeding turn to be downward or right-down. The second player's strategy is to always move the king rightward, which forces the first player to always move the king downward or right-down. If the king is in $(2k-2, k-1)$, we repeat the strategy for $k \coloneq k - 1$. Otherwise, the king is now in $(m, n) \coloneq (2k-1, k-2)$ for which $m > 2n$. If the first player could move, since he must move downward (to $(m, n - 1)$) or right-down (to $(m - 1, n - 1)$), which decreases the $y$ coordinate, then $n > 0$, which means $2 \le 2n < m$, so after that the second player can also move (to $(m', n') \coloneq (m - 1, n - 1)$ or $(m - 2, n - 1)$), and the new coordinate still satisfies $m' > 2n'$. This means the second player can always guarantee a move whenever the first player can move. Since the game must stop, therefore the one that couldn't move is the first player.
Remark. The winning/losing condition can be immediately seen by filling the DP table from the bottom right corner of the table. For each cell $(x, y)$, we store three boolean variables $(a(x, y), b(x, y), c(x, y))$ where $a$, $b$, and $c$ states whether the first player wins if he moves the chess king from $(x, y)$ one square right, down, or right-down diagonally, respectively. The DP transition is as follows:
\begin{align*}
a(x, y) &= (\neg b(x - 1, y)) \land (\neg c(x - 1, y)), \\
b(x, y) &= (\neg a(x, y - 1)) \land (\neg c(x, y - 1)), \\
c(x, y) &= (\neg a(x - 1, y - 1)) \land (\neg b(x - 1, y - 1)).
\end{align*}