IMO 1993 · Problem 3

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.

Official text of the problem. Official problem paper (PDF)

Answer

\[ \boxed{\text{All positive integers }n\text{ not divisible by }3.} \]

Solution

Identify the squares with points \((x,y)\in\mathbb Z^2\).

First, colour each square according to the residue of \(x+y\) modulo \(3\). Every jump involves exactly one square of each colour: two occupied squares become empty, and one empty square becomes occupied. Thus every move reverses the parity of all three colour counts.

If \(3\mid n\), the initial square contains exactly \(n^2/3\) pieces of each colour. The three colour counts therefore have the same parity, and this remains true after every move. A configuration consisting of one piece has colour counts \(1,0,0\) in some order, whose parities are not all equal. Hence \(3\mid n\) is impossible.

We now construct solutions for all other \(n\).

A three-piece removal operation. Let \(e,f\) be perpendicular unit lattice vectors. Suppose the squares \[ A,\quad A+e,\quad A+2e,\quad B=A+f \] are occupied, while \(C=A-f\) is empty. Make the three jumps \[ B\longrightarrow C,\qquad A+2e\longrightarrow A,\qquad C\longrightarrow B. \] These are legal: their jumped-over squares are respectively \(A,A+e,A\). At the end, the three pieces at \(A,A+e,A+2e\) have disappeared, and the supporting piece at \(B\) has returned to its original position. Every other square is unchanged.

Removing a strip. Suppose \(h\ge3\), all squares \[ (x,y),\qquad 0\le x\le2,\quad 0\le y\le h-1, \] are occupied, and \((3,0)\) is also occupied. Assume that \((0,h)\) and \((-1,0)\) are empty. We can remove the entire \(3\) by \(h\) strip while leaving every other piece unchanged.

Indeed, for \[ y=h-1,h-2,\ldots,3, \] remove the horizontal triple \[ (0,y),(1,y),(2,y) \] using the supporting piece \((0,y-1)\) and the empty square \((0,y+1)\). The latter is either the initially empty square \((0,h)\), or a square cleared at the preceding step.

There remains a \(3\) by \(3\) block. For \(x=0,1,2\), in that order, remove the vertical triple \[ (x,0),(x,1),(x,2) \] using the supporting piece \((x+1,0)\) and the empty square \((x-1,0)\). Again, the required empty square is either initially empty or has already been cleared. The final supporting piece is \((3,0)\), which is preserved.

Now start with a full \(N\) by \(N\) square \[ \{0,1,\ldots,N-1\}^2,\qquad N\ge6. \] Remove its leftmost three columns by this procedure, using \((3,0)\) as the final supporting piece. Then use the rotated procedure to remove the bottom three rows of the remaining rectangle. This second strip has length \(N-3\ge3\), its final supporting piece is \((3,3)\), and its required exterior empty squares are \((N,0)\) and \((3,-1)\).

The remaining configuration is exactly \[ \{3,4,\ldots,N-1\}^2, \] a full square of side \(N-3\), with no pieces elsewhere.

Consequently, for \(3\nmid n\), it suffices to solve the four cases \(n=1,2,4,5\).

For \(n=1\), there is already one piece. For \(n=2\), starting with \(\{0,1\}^2\), make the jumps \[ (0,0)\longrightarrow(2,0),\qquad (0,1)\longrightarrow(2,1),\qquad (2,0)\longrightarrow(2,2). \] Only the piece at \((2,2)\) remains.

For \(n=4\) and \(n=5\), the following diagrams give complete constructions using the three-piece removal operation. Every displayed square initially contains a piece. Remove the three squares labelled \(1\), then those labelled \(2\), and so on. An arrow at an endpoint of a triple points towards its supporting piece; the square immediately opposite that arrow is the required empty square. The star marks the piece that remains.

\[ n=4:\quad \begin{array}{cccc} * & 3^{\downarrow} & 3 & 3\\ 5^{\uparrow} & 5 & 5 & 4^{\leftarrow}\\ 2^{\uparrow} & 2 & 2 & 4\\ 1^{\uparrow} & 1 & 1 & 4 \end{array} \qquad n=5:\quad \begin{array}{ccccc} 3 & 4 & 5^{\downarrow} & 5 & 5\\ 3 & 4 & 6^{\downarrow} & 6 & 6\\ 3^{\rightarrow} & 4^{\rightarrow} & * & 8^{\leftarrow} & 7\\ 2^{\uparrow} & 2 & 2 & 8 & 7\\ 1^{\uparrow} & 1 & 1 & 8 & 7^{\leftarrow} \end{array} \]

To verify legality, observe that each label occurs on three consecutive squares. Every arrow points to a square bearing a larger label or a star, so its supporting piece is still present. The square opposite the arrow lies outside the displayed square or bears a smaller label, so it is empty. Thus every indicated removal is legal, and each diagram reduces to its single starred piece.

This proves the claimed characterization.

The solution was checked against John Scholes' IMO solution archive (Kalva).