IMO 1993 Problem 3

On an infinite chessboard, a solitaire game is played as follows: at the start, we have $n^2$ pieces occupying a square of side $n.$ The only allowed move is to jump over an occupied square to an unoccupied one, and the piece which has been jumped over is removed. For which $n$ can the game end with only one piece remaining on the board?

===================================

It is only possible when $n$ is not divisible by $3$. In these cases, apply an operation that removes $3$ consecutive pieces. If $n=3k+1$ we can delete the first and last columns and rows to reduce to $n$ to $3k-1$. If $n=3k+2$ then we delete the first two columns and rows to reduce $n$ to $3k-2$.

Suppose that $n$ is divisible by $3$, let $k:=n^2/3$. Color the squares with $1$, $2$, and $3$ so that every $3\times3$ grid has exactly $3$ squares of color $1$, $2$, and $3$. Suppose that we can end the game with only a piece of color $1$. Let $b_{12}$, $b_{13}$, and $b_{23}$ be the total number of jumps that increase the number of pieces of color $3$, $2$, and $1$, respectively. We then have $$b_{12}+b_{13}-b_{23}=k-1,$$ $$b_{23}+b_{13}-b_{12}=k,$$ $$b_{12}+b_{23}-b_{13}=k.$$ We get $b_{12}=b_{13}=k-1/2\notin\mathbb{Z}$, a contradiction.