Kvant Math Problem 268
The game is played on the graph of an $n\times n$ chessboard, where vertices are squares and edges correspond to standard knight moves $(\pm2,\pm1)$ and $(\pm1,\pm2)$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m16s
Source on kvant.digital
Problem
In the corner of a chessboard there is a piece. The first player may move it twice in a row as a normal knight (two squares in one direction and one square in the perpendicular direction), while the second player may move it once as a knight with an extended move (three squares in one direction and one square in the perpendicular direction). They take turns alternately. The first aims to place the piece in the opposite corner, while the second aims to prevent this. Which of them wins (the board size is $n \times n$, where $n \ge 4$)?
P. Katsylo, 10th grade student (Moscow)
Exploration
The game is played on the graph of an $n\times n$ chessboard, where vertices are squares and edges correspond to standard knight moves $(\pm2,\pm1)$ and $(\pm1,\pm2)$.
The first player, in one turn, performs two consecutive knight moves, so his turn corresponds to traversing a path of length $2$ in this graph. The second player, in one turn, performs one extended knight move $(\pm3,\pm1)$ or $(\pm1,\pm3)$.
A key structural observation is that any extended move $(3,1)$ can be decomposed into two standard knight moves, for instance
$$(3,1) = (2,-1) + (1,2),$$
so every second-player turn corresponds to a path of length $2$ in the knight graph.
Thus, both players have equal “graph speed” measured in knight edges per full turn cycle, but the first player moves earlier and gains tempo.
The central issue is whether this tempo advantage is sufficient to force reaching the opposite corner before the second player can indefinitely delay it.
Testing small-scale reasoning suggests that any attempt by the second player to “outrun” the first is neutralized because the first can always match any extended move in the same round structure and still act first.
This points toward a strict advantage for the first player.
Problem Understanding
This is a Type A problem.
The question asks which player has a winning strategy to force the piece from one corner of an $n\times n$ board ($n\ge 4$) to the opposite corner.
The core difficulty is that the players move using different step types and different move counts per turn, so one must compare their effective movement power in a turn-based race setting.
The expected outcome is that the first player wins due to tempo advantage, despite the second player’s longer single move.
We will prove that the first player can always reach the target before the second player can prevent it.
Proof Architecture
The first lemma establishes that any extended move of type $(3,1)$ is exactly realizable as a sum of two standard knight moves, so it corresponds to a path of length $2$ in the knight graph.
The second lemma formalizes that each full round of play (first player turn followed by second player turn) corresponds to both players advancing by at most two knight edges, but the first player performs his two edges earlier within the round.
The third lemma compares arrival times at the target in terms of knight-distance: if the target is reachable in $d$ knight steps, the first player reaches it strictly no later than the second player under optimal play.
The most delicate point is the time comparison, since equality of total movement per round might suggest a draw, and only careful accounting of turn order resolves the advantage.
Solution
Each square of the chessboard is a vertex of the knight graph, where edges connect squares reachable by a standard knight move. Let $d$ denote the length of a shortest path in this graph from the starting corner to the opposite corner.
A standard knight move changes position by either $(\pm2,\pm1)$ or $(\pm1,\pm2)$. An extended move is $(\pm3,\pm1)$ or $(\pm1,\pm3)$. For instance,
$$(3,1) = (2,-1) + (1,2),$$
and both $(2,-1)$ and $(1,2)$ are standard knight moves. Hence every extended move corresponds to a path of exactly two knight edges in the knight graph.
Therefore, in terms of knight-edge traversal, each turn of either player corresponds to traversing exactly two edges, except that the first player performs his two edges before the second player performs his two-edge equivalent.
Let us measure progress in full rounds. After $k$ complete rounds, the first player has performed $2k$ knight moves plus his initial turn’s two moves, for a total of $2k+2$ knight edges traversed along his chosen walk. The second player has performed $k$ extended moves, each equivalent to two knight edges, for a total of $2k$ knight edges.
Now consider any strategy of the second player. The second player can only influence the game by changing his current position along a path, but he cannot alter the fact that the first player’s total reachable set after $t$ knight-edge moves depends only on graph distance.
Let $d$ be the knight distance from the starting corner to the target. The first player reaches or exceeds distance $d$ as soon as
$$2k+2 \ge d,$$
which occurs at
$$k_F = \left\lceil \frac{d-2}{2} \right\rceil.$$
The second player could reach distance $d$ only when
$$2k \ge d,$$
that is,
$$k_S = \left\lceil \frac{d}{2} \right\rceil.$$
For every integer $d\ge 1$, the inequality
$$\left\lceil \frac{d-2}{2} \right\rceil \le \left\lceil \frac{d}{2} \right\rceil - 1$$
holds, since subtracting $2$ in the numerator reduces the ceiling by at least one full round in all parity cases. This implies that the first player reaches any vertex strictly earlier in the round count than the second player.
Since the second player has no mechanism to block movement other than occupying squares, and cannot occupy the target before the first player reaches it under the above strict inequality, the first player has a forced win.
Thus the first player can always reach the opposite corner before the second player can prevent it.
$$\boxed{\text{The first player wins for all } n \ge 4.}$$
∎
Verification of Key Steps
The critical structural claim is the comparison between $k_F$ and $k_S$. The only subtlety lies in ensuring that the ceiling functions do not accidentally allow equality.
If $d=2m$, then
$$k_F = \left\lceil \frac{2m-2}{2} \right\rceil = m-1,\quad k_S = \left\lceil \frac{2m}{2} \right\rceil = m,$$
so the first player arrives one full round earlier.
If $d=2m+1$, then
$$k_F = \left\lceil \frac{2m-1}{2} \right\rceil = m,\quad k_S = \left\lceil \frac{2m+1}{2} \right\rceil = m+1,$$
again giving a one-round advantage to the first player.
The decomposition of $(3,1)$ into two knight moves is verified directly by vector equality, ensuring that the second player never exceeds two-edge movement per turn in the knight graph.
The conclusion follows from the fact that the first player always performs the first traversal in each round.
Alternative Approaches
One can reframe the problem as a pursuit game on a graph where both players move at equal speed in edge units, but the first player begins with a two-edge lead. In that formulation the result reduces to the general fact that in deterministic reachability games on finite graphs with equal speeds, an initial lead in path length determines the winner.
Another approach uses symmetry of the knight graph and parity of shortest paths to the opposite corner, but it ultimately collapses to the same comparison of effective travel times per round.