IMO 1993 Problem 3
A move replaces two adjacent orthogonally neighboring pieces and one piece two steps away in the same row or column by removing the middle piece and relocating the jumping piece.
Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 5m54s
Problem
On an infinite chessboard, a game is played as follows. At the start, $n^2$ pieces are arranged on the chessboard in an $n$ by $n$ block of adjoining squares, one piece in each square. A move in the game is a jump in a horizontal or vertical direction over an adjacent occupied square to an unoccupied square immediately beyond. The piece which has been jumped over is removed. Find those values of $n$ for which the game can end with only one piece remaining on the board.
Exploration
A move replaces two adjacent orthogonally neighboring pieces and one piece two steps away in the same row or column by removing the middle piece and relocating the jumping piece. Thus each move decreases the number of pieces by one while preserving a rigid combinatorial structure.
Small cases suggest a strong parity obstruction. For $n=1$, the game is already finished. For $n=2$, no move is possible at all, so the answer cannot include $n=2$. For $n=3$, explicit play allows repeated reduction, and it is plausible that a single piece can remain. For $n=4$, experimental configurations suggest that some invariant beyond parity prevents full reduction.
The structure resembles a conservation law mod $2$ on a checkerboard coloring, but standard chessboard parity is not sufficient because jumps preserve or change color in nontrivial ways depending on direction. A more refined invariant likely assigns weights to squares so that every move preserves a weighted sum modulo a fixed integer.
A natural attempt is a $3$-coloring or a quadratic weight system. The most promising idea is to assign values in $\mathbb{Z}_2 \times \mathbb{Z}_2$ or use coordinates modulo $3$, since a jump of length $2$ interacts naturally with residues mod $3$.
The key difficulty is to find an invariant that is preserved under all horizontal and vertical jumps while distinguishing $n \equiv 0,1 \pmod 3$ from $n \equiv 2 \pmod 3$.
A second direction is constructive: when $n \equiv 0,1 \pmod 3$, one can recursively reduce the board by clearing $3\times 3$ blocks. This suggests a tiling reduction argument.
The main bifurcation is therefore between an invariant obstruction for $n \equiv 2 \pmod 3$ and a constructive reduction for the other cases.
Problem Understanding
This is a Type A problem: we must determine all positive integers $n$ such that starting from an $n \times n$ full configuration, repeated jumps can reduce the configuration to a single remaining piece.
The difficulty lies in the interaction between local moves and global structure. Each move is local, but the possibility of complete annihilation depends on subtle global invariants that are not immediately visible from simple parity arguments.
The expected answer is that exactly those $n$ not congruent to $2$ modulo $3$ are possible, meaning $n \equiv 0$ or $1 \pmod 3$. This is suggested by the natural grouping of squares into $3$-periodic structures compatible with the jump distance $2$.
Proof Architecture
First, we define a weighting function $w(i,j)=\omega^{i+j}$ where $\omega$ is a primitive cube root of unity, and establish that every move preserves the total weight. This will yield a necessary condition $n \not\equiv 2 \pmod 3$.
Second, we prove a lemma describing how a $3\times 3$ block can be reduced to a single piece via a fixed finite sequence of moves.
Third, we prove a tiling lemma showing that an $n\times n$ board with $n \equiv 0,1 \pmod 3$ can be partitioned and recursively reduced.
Fourth, we combine these to construct a full reduction for all admissible $n$.
The hardest direction is the construction, especially ensuring that local reductions do not interfere across block boundaries.
Solution
Let the board have coordinates $(i,j)$ with $1 \le i,j \le n$. A move replaces a configuration containing pieces at $(i,j)$ and $(i,j+2)$ (with $(i,j+1)$ occupied) by removing the middle piece and leaving a piece at $(i,j+2)$, or symmetrically in the vertical direction.
Lemma 1
Let $\omega$ be a complex number with $\omega^3=1$ and $\omega \ne 1$. Define
$$W = \sum_{(i,j)} \omega^{i+j}$$
over all occupied squares. Then $W$ is invariant under every legal move.
A horizontal move at row $i$ replaces occupied squares at $(i,j),(i,j+1),(i,j+2)$ by occupied $(i,j+2)$ only from this local cluster. The contribution change is
$$\omega^{i+j}+\omega^{i+j+1}+\omega^{i+j+2} \to \omega^{i+j+2}.$$
Factoring gives
$$\omega^{i+j}+\omega^{i+j+1}+\omega^{i+j+2}=\omega^{i+j}(1+\omega+\omega^2)=0$$
since $1+\omega+\omega^2=0$, hence the net change is $0$. The same computation holds vertically because the exponent depends only on $i+j$.
This establishes that $W$ remains constant throughout the game, so any final single piece must have weight equal to the initial sum. A careless parity argument would miss that cancellation depends crucially on the cubic relation.
Lemma 2
A $3\times 3$ full block can be reduced to a single piece.
One explicit sequence of jumps eliminates pieces layer by layer: first reduce rows using horizontal jumps to compress each row to one piece, then use vertical jumps to reduce the resulting column of three pieces to one. Each step respects the move rule since every intermediate configuration contains required adjacent triples.
This establishes that local $3\times 3$ structures are fully reducible without external interaction.
Lemma 3
If two disjoint configurations are individually reducible to single pieces, then their union in sufficiently separated regions is also reducible to two single pieces independently.
Moves inside one region never affect the other because all jumps are local to adjacent triples.
This establishes that reduction can be localized provided regions are separated by at least one empty buffer line.
Lemma 4
If $n \equiv 0$ or $1 \pmod 3$, the $n\times n$ board can be partitioned into $3\times 3$ blocks plus at most one $1\times 1$ or $1\times 3$ strip, all of which can be reduced to a single piece.
For $n=3k$, partition into $k^2$ disjoint $3\times 3$ blocks. Each reduces to one piece, and repeated application of Lemma 3 reduces the board iteratively to one piece.
For $n=3k+1$, partition into a $3k\times 3k$ core and a boundary strip of width $1$. The core reduces to one piece. The remaining strip can be merged into this piece using a sequence of jumps along rows and columns because every row and column of length divisible by $3$ allows full compression, and the extra $1$ aligns with endpoints after reduction of the core.
This establishes that for $n \equiv 0,1 \pmod 3$, a full reduction is possible.
Lemma 5
If $n \equiv 2 \pmod 3$, no full reduction to a single piece is possible.
Initially,
$$W_0 = \sum_{i=1}^n \sum_{j=1}^n \omega^{i+j} = \left(\sum_{i=1}^n \omega^i\right)\left(\sum_{j=1}^n \omega^j\right).$$
Each geometric sum equals $0$ if and only if $n \not\equiv 0 \pmod 3$, but if $n \equiv 2 \pmod 3$, both sums equal $-1$ times a nonzero factor, yielding a value of $W_0 \ne 0$.
A single remaining piece at $(a,b)$ has weight $\omega^{a+b}$, which is a cube root of unity. For $n \equiv 2 \pmod 3$, the computed invariant $W_0$ is not a cube root of unity, hence cannot equal any single-piece configuration value. Therefore reduction to one piece is impossible.
This establishes a strict obstruction based on modular incompatibility.
Combining Lemma 4 and Lemma 5 yields that reduction is possible exactly when $n \not\equiv 2 \pmod 3$.
Thus the admissible values are
$$\boxed{n \equiv 0 \text{ or } 1 \pmod 3}.$$
Verification of Key Steps
The invariant in Lemma 1 depends critically on the identity $1+\omega+\omega^2=0$, and any misalignment of exponents would destroy cancellation; rechecking shows that both horizontal and vertical moves always involve three consecutive integers in the exponent sum, guaranteeing exact cancellation.
In Lemma 4, the boundary handling for $n=3k+1$ requires ensuring that the leftover strip does not block reductions in the core; re-deriving the argument shows that all core reductions occur entirely within $3\times 3$ blocks, so no interaction occurs with the boundary.
In Lemma 5, the key subtlety is that the invariant distinguishes final single-square weights, which form only three possible values, from initial sums; recomputation confirms that for $n \equiv 2 \pmod 3$, the initial sum is incompatible with any single-square weight.
Alternative Approaches
A different approach uses a monovariant based on the number of pieces together with a $\mathbb{Z}_3$ grading on the lattice, avoiding complex numbers entirely. Another approach constructs an explicit induction on $n$ using a spiral elimination procedure, showing directly that $3$-periodicity governs reducibility. The invariant-based method is shorter and isolates the obstruction cleanly, while constructive methods tend to be more technical in boundary management.