IMO 1993 SL 5

Origin: FIN

Problem

On an infinite chessboard, a solitaire game is played as follows: At the start, we have n2 pieces occupying n2 squares that form a square of side n. The only allowed move is a jump horizontally or vertically over an occupied square to an unoccupied one, and the piece that has been jumped over is removed. For what positive integers n can the game end with only one piece remaining on the board?

Solution

For n = 1 the game is trivially over. If n = 2, it can end, for example, in the following way: • • • • −\to • • −\to • Fig. 1 The sequence of moves shown in Fig. 2 enables us to remove three pieces placed in a 1 \times 3 rectangle, using one more piece and one more free cell. In that way, for any n \geq4 we can reduce an (n + 3) \times (n + 3) square to an n \times n square (Fig. 3). Therefore the game can end for every n that is not divisible by 3. • • • • −\to • • • −\to • • −\to • Fig. 2 Fig. 3 Suppose now that one can play the game on a 3k\times3k square so that at the end only one piece remains. Denote the cells by (i, j), i, j \in{1, . . . , 3k}, and let S0, S1, S2 denote the numbers of pieces on those squares (i, j) for

which i+j gives remainder 0, 1, 2 respectively upon division by 3. Initially S0 = S1 = S2 = 3k2. After each move, two of S0, S1, S2 diminish and one increases by one. Thus each move reverses the parity of the Si’s, so that S0, S1, S2 are always of the same parity. But in the final position one of the Si’s must be equal to 1 and the other two must be 0, which is impossible.