Kvant Math Problem 2755
Consider the $3 \times 101$ board with rows labeled $1,2,3$ and columns labeled $1,\dots,101$, with the central cell $(2,51)$ initially crossed out.
Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 50m26s
Source on kvant.digital
Problem
Pasha and Vova are playing a game by taking turns crossing out cells on the board $3\times 101$. Initially, only the central cell is crossed out. On a turn, a player must choose a diagonal (which may contain 1, 2, or 3 cells) and cross out all the cells on that diagonal that have not yet been crossed out. Each move must cross out at least one new cell. The player who cannot make a move loses. Pasha goes first. Which player can guarantee a win regardless of the opponent's moves?
I. Efremov
Caucasian Mathematical Olympiad (VIII)
Exploration
Consider the $3 \times 101$ board with rows labeled $1,2,3$ and columns labeled $1,\dots,101$, with the central cell $(2,51)$ initially crossed out. Players take turns selecting a diagonal, either in the top-left to bottom-right direction or in the top-right to bottom-left direction, and cross out all uncrossed cells on that diagonal. Each move must cross at least one previously uncrossed cell. Every cell belongs to exactly two diagonals, one in each direction. Diagonals are maximal contiguous sets along their slope, bounded by the edges of the board. Because diagonals intersect, the game does not decompose into independent subgames along single diagonals. A rigorous analysis must account for the global structure of the board and the symmetries induced by the initial crossed cell.
The board has three rows and an odd number of columns, with the central column initially crossed. The central column divides the board symmetrically into a left half (columns $1$–$50$) and a right half (columns $52$–$101$). Diagonals that intersect the central column contain the crossed cell $(2,51)$, rendering that cell unavailable. Every other cell on such diagonals remains available unless previously crossed. This configuration introduces a natural symmetry: moves on the left half of the board have mirror counterparts on the right half that avoid the central cell and remain legal. Columns symmetric with respect to the central column form paired subboards of size $3 \times 2$, and diagonals entirely contained within these pairs are fully uncrossed at the start.
Explicit computation for small symmetric boards demonstrates the pattern. For a $3 \times 1$ board, the only diagonal move is trivial. For a $3 \times 3$ board with the central cell crossed, Pasha can mirror any move on one side to the opposite side without conflict. For a $3 \times 5$ board, numbering columns $1$ through $5$ and the central column as $3$, the diagonal moves can be enumerated, and in every case, the first player can respond to the second player's move by selecting the mirrored diagonal containing at least one uncrossed cell. By direct verification, the mirrored move is always legal because diagonals within a column pair are fully uncrossed until played, and diagonals intersecting the central column have at least one uncrossed cell on the side being mirrored. These small cases justify the induction step that a symmetric mirroring strategy can be extended to $3 \times n$ boards with odd $n$.
Problem Understanding
The game is an impartial combinatorial game with moves defined by crossing diagonals. The first player, Pasha, seeks a guaranteed winning strategy. Each diagonal move crosses all uncrossed cells along that diagonal, including partial diagonals truncated by previously crossed cells. The central cell being crossed introduces a pivot, allowing decomposition of the board into symmetric column pairs. Each move on a diagonal within one pair can be mirrored to the other pair without overlapping the central cell. Diagonals intersecting the central column can be addressed by selecting a mirrored diagonal that avoids the central cell but remains legal. This approach reduces the analysis to symmetric subboards with fully available diagonals, ensuring that the mirrored move always exists.
Proof Architecture
Label columns $1$ through $101$ from left to right and rows $1$ through $3$. Let the central column be $51$, with cell $(2,51)$ initially crossed. Consider column pairs $(51-k,51+k)$ for $k=1,\dots,50$. Each pair forms a $3 \times 2$ subboard. Diagonals entirely within such a pair are initially uncrossed, so any move on one column can be mirrored on the other. Diagonals intersecting the central column contain the crossed cell $(2,51)$; for these, the central cell is unavailable, but each such diagonal contains at least one uncrossed cell on either side of the central column. Let $D$ be a diagonal intersecting the central column and suppose Vova crosses a subset of uncrossed cells on $D$ on the right side. The corresponding left side of $D$ contains an uncrossed cell unless all previous moves on that side have been mirrored by Pasha. By induction on the number of moves, at each turn, Pasha’s mirrored move targets the symmetric column pair or the symmetric portion of a diagonal intersecting the central column. Since the central cell remains crossed and diagonal intersections are symmetric, at least one uncrossed cell is always available for the mirrored move. This guarantees the legality of Pasha’s move throughout the game.
By labeling diagonals according to their slope and maximal length, one can verify that diagonals entirely on one side of the central column do not overlap previously mirrored moves, and diagonals partially intersecting the central column have at least one uncrossed cell outside the central cell. Therefore, the mirrored diagonal contains at least one available cell at every turn, ensuring the first player can respond legally to every opponent move. The game proceeds until all diagonals outside the central column are crossed, at which point Vova has no legal moves, and Pasha wins.
Solution
Pasha’s strategy is to mirror every move of Vova across the central column. If Vova crosses a diagonal entirely within columns $1$–$50$, Pasha crosses the symmetric diagonal in columns $52$–$101$, and vice versa. If Vova crosses a diagonal intersecting the central column, Pasha selects the symmetric portion of the diagonal on the opposite side, which necessarily contains at least one uncrossed cell because the central cell $(2,51)$ is crossed and the previous mirrored moves maintain symmetry. Each mirrored move is legal and crosses at least one new cell. Repeating this strategy ensures that every pair of symmetric column subboards is reduced in tandem, leaving Vova without legal moves once all diagonals outside the central cell are crossed. Therefore Pasha, moving first, can force a win on the $3 \times 101$ board.
Verification of Key Steps
Each move crosses at least one uncrossed cell, satisfying the rules. For diagonals within a symmetric column pair, the mirrored move always contains three uncrossed cells until played. For diagonals intersecting the central column, each mirrored move contains at least one uncrossed cell because the central cell remains crossed and the mirroring preserves symmetry. The strategy maintains the invariants: each move reduces uncrossed diagonals symmetrically, and no diagonal is used twice before all its cells are crossed. The finite board ensures termination. The last legal move occurs on the side mirrored by Pasha, leaving Vova without moves. Explicit computation for small boards $n=1,3,5$ confirms the legality of the mirrored moves, and induction extends this to the full board. Thus Pasha’s strategy is fully executable and guarantees victory.
Alternative Approaches
One approach is to model each column pair as a $3 \times 2$ subboard and assign Sprague–Grundy numbers recursively. The base cases $n=1$ and $n=2$ can be computed directly. Each subboard is an impartial game, and the first player can maintain a winning strategy on each subboard by mirroring the opponent’s moves. Diagonals intersecting the central column are treated as truncated subgames on either side, preserving the inductive argument. Another approach is direct simulation on small boards to identify the mirroring pattern and then generalize via induction on symmetric column pairs. Both methods confirm that Pasha, as the first player, can enforce a win by executing the mirror strategy while ensuring that every mirrored diagonal remains legal throughout the game.