Problem 3

On an infinite chessboard, start with

n^2

pieces in an

n

n

block, one per square. A move jumps horizontally or vertically over an adjacent occupied square to the unoccupied square immediately beyond, removing the jumped piece. Find those values of

n

for which the game can end with only one piece remaining.

Step 4 of 4: Iterate the reduction

Previous step Next step

In plain words

The local gadget turns the modular classification into a global construction.

n=1,2\pmod3\Longrightarrow\text{one piece remains}

Detailed analysis

Partition an n by n block into successive 3-wide strips plus a 1-wide or 2-wide remainder. Apply the strip lemma alternately in the two directions. The remainder is a 1 by 1 terminal for n congruent to 1, and the same two-direction gadget reduces the congruent-to-2 remainder to that terminal. Thus every n not divisible by 3 is solvable; together with the invariant, precisely n not divisible by 3 work.