Maths Olympiad Prep

Library / /30 of 106

Combinatorics Difficulty 8.1 Shortlist Find the answer

On an infinite chessboard, a solitaire game is played as follows: at the start, we have n2n^2 pieces occupying a square of side n.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 nn can the game end with only one piece remaining on the board?

A number or a short expression. Spacing and $ signs are ignored.

Solution

To determine for which values of n n the game can end with only one piece remaining, we must analyze the rules and structure of the solitaire game on an infinite chessboard.

Initially, the board is filled with n2 n^2 pieces occupying a square of side n n . The only allowed move is a jump over an adjacent occupied square to land on an unoccupied square, after which the jumped-over piece is removed.

We note the following:

1. Parity Argument: Consider coloring the chessboard in a checkerboard pattern where squares in one color are assigned a label, say 1, and the other color, a label 0. Since the move of jumping over a piece necessarily requires that the jump starts and ends on squares of the same color, this invariant (preserving the count of each color's occupancy modulo 2) can prevent certain final configurations based on the starting n n .

2. **Modulo 3 3 Analysis**: We exploit the idea that, given the pattern of jumps, ending with a single piece means effectively removing a majority of the pieces. The number of occupied pieces on a square of side n n aligns with n2 n^2 .

3. Consider the sequence of legal jumps designed to reduce the total number of pieces from n2 n^2 down to 1. Each jump removes one additional piece. Observe the requirement based on game configuration: the distinction in the number modulo 3 alterations throughout the course of jumps depends on the ability to sequence such removals effectively. This can only be balanced if n n is not divisible by 3, where symmetries don't obstruct the removal of pieces down to the last one.

4. Conclusion: By setting up a board of n×n n \times n, making sure the total n2 n^2 pieces can be sequentially reduced correctly into one via legal moves, practically signifies needs for non-divisibility by 3, otherwise encountering unavoidable symmetrical deadlocks.

Therefore, the values of n n for which the game can end with only one piece on the board are precisely those values where:

n is not divisible by 3. n \text{ is not divisible by } 3.

Thus, the general solution in terms of n n is:

n not divisible by 3. \boxed{n \text{ not divisible by } 3}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.