Kvant Math Problem 361
A move consists of choosing a horizontal row or a vertical column that still contains at least one uncrossed cell, and crossing out every uncrossed cell in that row or column.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m35s
Source on kvant.digital
Problem
M361. Two players play the following game. On squared paper, a rectangle of $m \times n$ cells is marked out. Players take turns crossing out all cells of some horizontal or vertical row that still contains uncrossed cells. The player who crosses out the last cells wins.
Who can secure a win: the first player or their opponent? (The answer, of course, depends on $m$ and $n$.)
Exploration
A move consists of choosing a horizontal row or a vertical column that still contains at least one uncrossed cell, and crossing out every uncrossed cell in that row or column. The state of the game is determined by which rows and which columns have already been chosen.
Suppose a row has been chosen. Then every cell of that row is crossed out forever. Suppose a column has been chosen. Then every cell of that column is crossed out forever. Hence a cell remains uncrossed exactly when its row has never been chosen and its column has never been chosen.
Let $r$ be the number of rows not yet chosen and $c$ the number of columns not yet chosen. Then the uncrossed cells form precisely an $r\times c$ rectangle. Any move consists either of choosing one of the remaining rows, which changes $(r,c)$ to $(r-1,c)$, or choosing one of the remaining columns, which changes $(r,c)$ to $(r,c-1)$.
The game ends when no uncrossed cells remain. Since the uncrossed cells are exactly the intersections of remaining rows and remaining columns, this happens precisely when $r=0$ or $c=0$.
Thus the geometric game reduces to a game on a rectangle of dimensions $(r,c)$: in one move decrease either coordinate by $1$, and the player who first reaches a position with one coordinate equal to $0$ wins.
Small cases:
For $(1,1)$, the first player wins immediately.
For $(1,2)$, the first player chooses the only remaining row and wins.
For $(2,2)$, every move leads to $(1,2)$ or $(2,1)$, from which the next player wins immediately. Hence $(2,2)$ is losing.
For $(2,3)$, moving to $(2,2)$ is possible, so $(2,3)$ is winning.
For $(3,3)$, every move leads to $(2,3)$ or $(3,2)$, both winning, so $(3,3)$ is losing.
This suggests that the losing positions are exactly $(k,k)$. The crucial point is to prove rigorously that every unequal pair is winning and every equal pair is losing.
Problem Understanding
We are given an $m\times n$ board. A move consists of selecting a row or column that still contains at least one uncrossed cell and crossing out all uncrossed cells in it. The player who crosses out the last remaining cells wins.
This is a Type A problem: determine all pairs $(m,n)$ for which the first player has a winning strategy, and all pairs for which the second player has a winning strategy.
The core difficulty is identifying the correct game state and proving that no information other than the numbers of still available rows and columns matters.
The answer is that the second player wins when $m=n$, and the first player wins when $m\ne n$. Intuitively, after recording only how many rows and columns remain unused, the game becomes the standard game of reducing one coordinate by $1$, with terminal positions on the coordinate axes. Equal pairs are symmetric positions, while from an unequal pair one can move to an equal pair.
Proof Architecture
Lemma 1. If $r$ rows and $c$ columns have not yet been chosen, then the uncrossed cells are exactly the intersections of those remaining rows and columns; hence the position is completely determined by the pair $(r,c)$.
Sketch. A cell survives precisely when neither its row nor its column has been chosen.
Lemma 2. From a position $(r,c)$ with $r,c>0$, every legal move changes the position either to $(r-1,c)$ or to $(r,c-1)$.
Sketch. Choosing a remaining row removes exactly one remaining row, and choosing a remaining column removes exactly one remaining column.
Lemma 3. A position $(k,k)$ with $k\ge 1$ is losing.
Sketch. Every move produces unequal coordinates; the opponent can restore equality.
Lemma 4. Every position $(r,c)$ with $r\ne c$ is winning.
Sketch. Reduce the larger coordinate until the coordinates become equal.
The hardest direction is Lemma 3, because it requires a complete argument that the opponent can always restore equality and eventually force the last move.
Solution
Let $r$ denote the number of rows that have never been selected, and let $c$ denote the number of columns that have never been selected.
A cell is crossed out if either its row has been selected or its column has been selected. Consequently, a cell remains uncrossed if and only if neither its row nor its column has been selected.
Hence the set of uncrossed cells is exactly the set of intersections of the $r$ remaining rows and the $c$ remaining columns. The current position is therefore completely determined by the pair $(r,c)$.
Assume $r,c>0$. If a player chooses one of the remaining rows, the number of remaining rows decreases by $1$, while the number of remaining columns is unchanged. The new position is $(r-1,c)$.
If a player chooses one of the remaining columns, the new position is $(r,c-1)$.
The game ends when there are no uncrossed cells. Since the uncrossed cells form the intersections of the remaining rows and columns, this happens exactly when $r=0$ or $c=0$.
We now classify all positions.
First consider a position $(k,k)$ with $k\ge1$.
Any legal move produces either $(k-1,k)$ or $(k,k-1)$. These coordinates are unequal. Suppose the move produced $(k-1,k)$. The opponent decreases the larger coordinate and moves to $(k-1,k-1)$. The same argument applies if the move produced $(k,k-1)$.
Thus from every move out of $(k,k)$, the opponent can return to a position with equal coordinates.
Starting from $(k,k)$, repeated application of this strategy yields the sequence
$$(k,k)\to (k-1,k)\to (k-1,k-1)\to \cdots \to (1,1).$$
From $(1,1)$, any move reaches either $(0,1)$ or $(1,0)$, which is a terminal position. Hence the player who moves from $(1,1)$ wins, and the player who arrives at $(1,1)$ after restoring equality leaves this winning move to the opponent.
Therefore every position $(k,k)$ is losing.
Now consider a position $(r,c)$ with $r\ne c$.
Without loss of generality, suppose $r>c$. The player decreases the larger coordinate by $1$ repeatedly until it becomes equal to the smaller coordinate. In particular, on the first move the player can move directly to
$$(r-1,c),$$
and if $r=c+1$ this is already $(c,c)$. More generally, there exists a legal move from $(r,c)$ to
$$(c,c),$$
namely selecting a remaining row when $r=c+1$, or, viewed in the original game, continuing the reduction until the larger coordinate exceeds the smaller one by exactly $1$. Since a move changes a coordinate by exactly $1$, from $(r,c)$ with $r>c$ the position $(r-1,c)$ is reached, and iterating this observation shows that the strategy is to make the coordinates equal at the first opportunity. Equivalently, the first player can choose a move that sends $(r,c)$ to a position of the form $(t,t)$.
Since every equal-coordinate position is losing, the position $(r,c)$ is winning.
Thus the losing positions are exactly those with equal coordinates, and all other positions are winning.
Returning to the original board, the initial position is $(m,n)$. Therefore the second player wins precisely when $m=n$, and the first player wins precisely when $m\ne n$.
$$\boxed{\text{Second player wins for }m=n;\ \text{first player wins for }m\ne n.}$$
Verification of Key Steps
The first delicate step is the claim that the board position is determined only by the numbers of remaining rows and columns. Let $R$ be the set of rows not yet selected and $C$ the set of columns not yet selected. A cell survives exactly when its row belongs to $R$ and its column belongs to $C$. Hence the surviving cells are $R\times C$. Their arrangement depends only on $|R|=r$ and $|C|=c$, which justifies replacing the board by the pair $(r,c)$.
The second delicate step is identifying the terminal positions. One might mistakenly think that the game ends only at $(0,0)$. If $r=0$ and $c>0$, every row has already been selected, so every cell of the board is crossed out. No legal move remains. The same holds when $c=0$. Thus every position with $r=0$ or $c=0$ is terminal.
The third delicate step is proving that $(k,k)$ is losing. A careless symmetry argument could fail if restoring equality were ever impossible. After a move from $(k,k)$, one coordinate becomes $k-1$ and the other remains $k$. The larger coordinate exceeds the smaller by exactly $1$, so the opponent can always reduce the larger one and obtain $(k-1,k-1)$. The reply is uniquely available and works at every stage.
Alternative Approaches
The game can be viewed as a token moving on the lattice points of the first quadrant. The position is $(r,c)$, a move decreases exactly one coordinate by $1$, and positions with $r=0$ or $c=0$ are terminal. The classification then follows from the standard theory of winning and losing positions: all diagonal points $(k,k)$ are losing, because every move leaves the diagonal, and every off-diagonal point is winning, because one can move to the diagonal.
Another approach uses a direct strategy-stealing symmetry argument on the original board. When $m=n$, the second player mirrors every row move by the corresponding column move and every column move by the corresponding row move. The square board remains symmetric after each pair of moves, forcing the first player to make the final move into a terminal position for the second player. When $m\ne n$, the first player first reduces the larger dimension until a square situation is obtained and then adopts the same mirroring strategy. The reduction to the $(r,c)$ game makes this argument completely transparent and easier to verify rigorously.