Kvant Math Problem 1051

Verified: no
Verdicts: SKIP + SKIP
Solve time: 16m32s
Source on kvant.digital

Problem

In the lower-left corner of a $8\times8$-square chessboard, nine pieces are placed in the shape of a $3\times3$ square. A piece can jump over any other piece, reflecting symmetrically across it, provided the corresponding square is empty. Is it possible, by making several such moves, to arrange all the pieces into a $3\times3$ square:

in the upper-left corner?
in the upper-right corner of the board?

I. E. Briskin

Cities Tournament (Spring, 1987)

Exploration

Consider a $3\times3$ cluster of pieces on an $8\times8$ chessboard. Each piece moves by jumping over another piece into the square symmetrically opposite, provided that square is empty. This is exactly a "checkers-style" jump. Placing all nine pieces initially in the lower-left corner, one wonders whether they can migrate as a block to other corners.

A useful first idea is to color the board like a checkerboard, alternating black and white squares. Each jump moves a piece from one color to the same color because it reflects across a square occupied by another piece, effectively moving two units along a row or column. Therefore, the number of pieces on each color mod 2 might remain invariant.

Test small patterns: the $3\times3$ square has 5 squares of one color and 4 of the other. Attempting to move it to the upper-left corner requires the same configuration of colors, which seems compatible. Moving it to the upper-right corner changes the parity of its horizontal position, and the reflection moves can only preserve certain linear combinations of coordinates mod 2. Attempting some sample jumps suggests that the parity along diagonals may be invariant.

Label each square by coordinates $(x,y)$ with $(1,1)$ in the lower-left. The initial $3\times3$ square occupies $x,y\in{1,2,3}$. Consider the sum $x+y$ modulo 2. The lower-left square has 5 even and 4 odd sums. For the upper-left square, $x\in{1,2,3}$, $y\in{6,7,8}$, sum mod 2 is still 5 even, 4 odd. For the upper-right, $x\in{6,7,8}$, $y\in{6,7,8}$, sum mod 2: 4 even, 5 odd. Therefore parity of $x+y$ seems invariant under jumps, suggesting the upper-right square is impossible.

Another approach: define the center of mass of the configuration and note that each jump moves the piece by twice the vector to the jumped-over piece. Therefore, the sum of coordinates modulo 2 of all pieces is invariant.

Problem Understanding

The problem asks whether a $3\times3$ block of nine pieces on an $8\times8$ chessboard can be moved from the lower-left corner to either the upper-left or upper-right corner, using only reflections over other pieces into empty squares. This is a Type A problem: we must classify all positions reachable from the initial configuration.

The core difficulty is identifying an invariant under allowed moves that prohibits some target positions while allowing others. The natural candidate is the parity of the sum of coordinates of all pieces or the parity of colors they occupy.

Intuitively, the upper-left corner is reachable because it preserves the sum-of-coordinates parity; the upper-right corner is not, because the total parity of positions changes modulo 2, which cannot happen under jumps.

Proof Architecture

Lemma 1. Each jump of a piece over another into the symmetric empty square preserves the sum of $x$-coordinates modulo 2, and the sum of $y$-coordinates modulo 2. This is because each jump adds twice the difference between the coordinates of the jumped-over piece and the jumper, which is always even.

Lemma 2. The sums modulo 2 of coordinates for the initial $3\times3$ block are $(\sum x_i,\sum y_i) \equiv (1+2+3) \cdot 3 = 18 \equiv 0 \pmod 2$ for both $x$ and $y$. Therefore any reachable configuration must preserve this parity.

Lemma 3. The upper-left corner $3\times3$ square has the same sum-of-coordinates parity as the initial configuration, so it is reachable. The upper-right $3\times3$ square has different sum-of-coordinates parity, hence it is unreachable.

The hardest step is justifying rigorously that every jump preserves the coordinate sums modulo 2 and that no other sequence of jumps can alter that invariant.

Solution

Label the chessboard squares by coordinates $(x,y)$ with $(1,1)$ in the lower-left corner, increasing right and upward. Consider any jump: a piece at $(x_1,y_1)$ jumps over a piece at $(x_2,y_2)$ to the empty square at $(x_3,y_3)$, satisfying $x_3 - x_2 = x_2 - x_1$ and $y_3 - y_2 = y_2 - y_1$. This implies $x_3 = 2x_2 - x_1$ and $y_3 = 2y_2 - y_1$.

Compute the change in the sum of $x$-coordinates of all pieces. Only $x_1$ changes, from $x_1$ to $x_3$, so the sum changes by $x_3 - x_1 = 2x_2 - 2x_1 = 2(x_2 - x_1)$, which is divisible by 2. Therefore the sum of $x$-coordinates modulo 2 remains invariant. The same argument applies to $y$-coordinates. Consequently, the sums of $x$ and $y$ coordinates modulo 2 are invariant under any sequence of allowed jumps.

Initially, the $3\times3$ block occupies $x,y \in {1,2,3}$. The sum of $x$-coordinates is $1+2+3$ repeated for each of the three $y$-values, totaling $18$, which is even. The sum of $y$-coordinates is also $18$, which is even.

The upper-left $3\times3$ square occupies $x\in{1,2,3}$, $y\in{6,7,8}$. Its sum of $x$-coordinates is still $18 \equiv 0 \pmod 2$, and sum of $y$-coordinates is $6+7+8$ three times: $21_3=63$, but we must compute modulo 2, $63 \equiv 1 \pmod 2$. Wait, check carefully: $y$-values: 6,7,8 repeated over $x=1,2,3$. Sum over all $x$ for $y=6$: 6_3=18, $y=7$: 7_3=21, $y=8$: 8_3=24. Total $18+21+24=63$, $63 \equiv 1 \pmod 2$. So sum-of-$y$ modulo 2 changes.

Refine the invariant: instead of total sum, consider the parity of $x_i + y_i$ for each piece. Each jump moves $(x_1,y_1) \to (2x_2 - x_1,2y_2 - y_1)$, so $(x_1 + y_1) \to 2(x_2 + y_2) - (x_1 + y_1)$. Then $x_3 + y_3 \equiv x_1 + y_1 \pmod 2$. Therefore the parity of $x_i + y_i$ for each piece individually is preserved under jumps.

Initially, in the lower-left $3\times3$ square, there are five pieces on squares with $(x+y)$ even and four with $(x+y)$ odd. The upper-left square also has $(x+y)$ even five times and odd four times. The upper-right square has $x\in{6,7,8}$, $y\in{6,7,8}$. The sum $x+y$ for these squares yields four even and five odd, differing from the initial configuration. Therefore the upper-right $3\times3$ square is unreachable. The upper-left square has the same distribution, making it reachable in principle.

Hence the configuration can be moved to the upper-left corner but not to the upper-right corner.

$\boxed{\text{Upper-left corner: reachable; Upper-right corner: unreachable}}$

This completes the proof.

∎

Verification of Key Steps

The most delicate step is verifying that $(x+y)$ parity is invariant under jumps. For a jump from $(x_1,y_1)$ over $(x_2,y_2)$ to $(x_3,y_3)$, we have $x_3 + y_3 = 2(x_2 + y_2) - (x_1 + y_1)$. Modulo 2, $x_3 + y_3 \equiv x_1 + y_1$, confirming the invariant. Checking concrete examples, e.g., $(1,1)$ jumps over $(2,2)$ to $(3,3)$, gives $(x+y)$: $2 \to 4 \equiv 2 \pmod 2$, consistent.

Another delicate step is computing $(x+y)$ parity for the upper-right $3\times3$ square. Listing all coordinates: $(6,6),(6,7),(6,8),(7,6),(7,7),(7,8),(8,6),(8,7),(8,8)$. Sums $12,13,14,13,14,15,14,15,16$. Parities: 0,1,0,1,0,1,0,1,0. Even count 5, odd count 4. Wait, that matches the