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.

Heard from Mohit Aron in 2020. He is my classmate from IIT Dehi and founder of Cohesity (and co-founder of Nutanix too). Mohit told me that this puzzle was the favorite puzzle of the Cohesity's Chief Architect. A couple of days later, I learnt that this problem was Problem 3 at IMO 1993.

Step 1: Let 1 denote an occupied square; let 0 denote n unoccupied square. Then a key step in the solution is to see that

0 1 1
0 1 x
0 1 x

can be transformed into

0 0 1
0 0 x
0 0 x

Step 2: Consider a 4x4 square (padded with zeros on all four sides) in which occupied squares are marked with symbols {1, 2, 3, 4, #} and unoccupied squares are marked with 0.

0 0 0 0 0 0 
0 1 2 2 2 0
0 1 # # 3 0
0 1 # # 3 0
0 4 4 4 3 0
0 0 0 0 0 0

We can use the four # signs to eliminate 1's (by converting them into zeros in three moves), then 2's, then 3's and finally the 4's.

Step 3: For 5x5 square, we may proceed as follows:

0 0 0 0 0 0 0
0 1 2 3 3 3 0
0 1 2 4 4 4 0
0 1 2 # 6 5 0
0 8 8 8 6 5 0
0 7 7 7 6 5 0
0 0 0 0 0 0 0

Somehow, I find it easier to see the pattern as follows:

0 0 0 0 0 0 0
0 1 1 2 2 2 0
0 1 1 2 2 2 0
0 1 1 # 3 3 0
0 4 4 4 3 3 0
0 4 4 4 3 3 0
0 0 0 0 0 0 0

Basically, in the 4x4 matrix, we strip an outer layer of width 1 to reduce the problem size. In the 5x5 case, this outer layer has width 2.

Step 4: Let's generalize:

(a) When n = 3k + 1, the outer layer is of width 1; stripping this outer layer (just like we did for the 4x4 matrix above), reduces the problem to a smaller square with n' = 3k - 1 = 3(k - 1) + 2.

(b) When n = 3k + 2, the outer layer is of width 2; stripping this outer layer (just like we did for the 5x5 matrix above) reduces the problem to a smaller square with n' = 3k - 2 = 3(k-1) + 1.

(c) Base case: we can solve the problem for n = 1 and n = 2.

Combining (a), (b) and (c), we may infer that a strategy for all n = 3k + 1 and n = 3k + 2 exists.

Step 5 We have to demonstrate that for n = 3k, no strategy exists.

Let's position the points of the n x n matrix at integer positions in x-y plane, with bottom left at the origin (0, 0). Next, let's divide points in the n x n matrix into 3 buckets depending on the value of (x+y) mod 3. Let the labels of these buckets be 0, 1, 2, respectively. For example, for the 5x5 matrix, the labels are:

1 2 0 1 2
0 1 2 0 1
2 0 1 2 0
1 2 0 1 2
0 1 2 0 1

What matters is this: how many points belong to each bucket? For example, for the

2x2 matrix: bucket sizes are <1, 2, 1>
3x3 matrix: bucket sizes are <3, 3, 3>
4x4 matrix: bucket sizes are <6, 5, 6>

In fact, the actual bucket size doesn't matter for the argument we develop below. Only the polarity matters: odd or even.

2x2 matrix: bucket sizes are <odd, even, odd>
3x3 matrix: bucket sizes are <even, even, even>
4x4 matrix: bucket sizes are <even, odd, even>

Step 6: Now let's study the allowable 'moves' in the problem: a point jump over its adjacent point as in a game of checkers (eliminating the point that was jumped over). With such a move, the polarity of each member of the bucket size sequence flips! :)

In other words,

<even, even, even> → <odd, odd, odd>
<odd, odd, odd> → <even, even, even>
<even, odd, even> → <odd, even, odd>
… and so on.

Now, the final desired configuration is <0, 0, 1> or <1, 0, 0> or <0, 1, 0>. In other words, two evens and one odd. Starting with <even, even, even> or <odd, odd, odd>, such a configuration is not reachable through a series of moves.

Step 7: What remains to be shown is that for 3k x 3k matrices, bucket size sequences are either <odd, odd, odd> or <even, even, even>. It is easy to see that

For 3x3 matrix, bucket sizes are <3, 3, 3>
For 6x6 matrix, bucket sizes are <12, 12, 12>
For 9x9 matrix, bucket sizes are <27, 27, 27>
… and so on, always of the form <p, p, p>.