IMO 1993/A3 solution

IMO 1993

Problem A3

On an infinite chessboard a game is played as follows. At the start n² pieces are arranged in an n x n block of adjoining squares, one piece on 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.

Solution

We show first that the game can end with only one piece if n is not a multiple of 3. Note first that the result is true for n = 2 or 4.

n=2


X X   . . X   . . X   . . . 

X X   X X     . . X   . . .

                          X

n = 4


              X         X         X         X         X

X X X X   X X . X   X X . X   . . X X   . . X X   . X . .

X X X X   X X . X   . . X X   . . X X   X . X X   X . X X

X X X X   X X X X   X X X X   X X X X   . X X X   . X X X

X X X X   X X X X   X X X X   X X X X   . X X X   . X X X



    X         X         X

. X . .   . X . .   . X X .   . X . .   . X . .   . . . .

X X . .   . . X .   . . . .   . . X .   . X X .   . . X .

. X X X   . X X X   . X . X   . X . X   . . . X   . X . X

. X X X   . X X X   . X X X   . X X X   . . X X   . . X X



. . . .   . . . .   . . . .   . . . .

. . X X   . X . .   . . . .   . . . .

. X . .   . X . .   . . . .   . . . .

. . X .   . . X .   . X X .   . . . X

The key technique is the following three moves which can be used to wipe out three adjacent pieces on the border provided there are pieces behind them:


 X X X     X X .     X X .     X X X

 X X X     X X .     . . X     . . .

               X         X

We can use this technique to reduce (r + 3) x s rectangle to an r x s rectangle. There is a slight wrinkle for the last two rows of three:


 X X X X     X X . X     . . X X     . . X X     . . . X     . . . X

 X X X X     X X . X     . . X X     . . X X     . . . X     . . . X

 . . . X     . . X X     . . X X     . X . .     . X X .     . . . X

Thus we can reduce a square side 3n+2 to a 2 x (3n+2) rectangle. We now show how to wipe out the rectangle. First, we change the 2 x 2 rectangle at one end into a single piece alongside the (now) 2 x 3n rectangle:


  X X    . .     . .

  X X    . .     . .

         X X        X

Then we use the following technique to shorten the rectangle by 3:


 X X X     X . X     X . X     . . .     . . .

 X X X     X . X     X . X     . . .     . . .

 X         X X     X .       X X . X         . X

That completes the case of the square side 3n+2. For the square side 3n+1 we can use the technique for removing 3 x r rectangles to reduce it to a 4 x 4 square and then use the technique above for the 4 x 4 rectangle.

Finally, we use a parity argument to show that if n is a multiple of 3, then the square side n cannot be reduced to a single piece. Color the board with 3 colors, red, white and blue:


 R W B R W B R W B ...

 W B R W B R W B R ...

 B R W B R W B R W ...

 R W B R W B R W B ...

 ...

Let suppose that the single piece is on a red square. Let A be the number of moves onto a red square, B the number of moves onto a white square and C the number of moves onto a blue square. A move onto a red square increases the number of pieces on red squares by 1, reduces the number of pieces on white squares by 1, and reduces the number of pieces on blue squares by 1. Let n = 3m. Then there are initially m pieces on red squares, m on white and m on blue. Thus we have:

- A + B + C = m-1; A - B + C = m; A + B - C = m.

Solving, we get A = m, B = m - 1/2, C = m - 1/2. But the number of moves of each type must be integral, so it is not possible to reduce the number of pieces to one if n is a multiple of 3.

Solutions are also available in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.

34th IMO 1993