Kvant Math Problem 1128
Consider first the case of a $2 \times 2$ chessboard with two pieces.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m33s
Source on kvant.digital
Problem
Several pieces are placed on a chessboard. In one move, a piece can be moved to an adjacent (horizontally or vertically) empty square. After several moves, it turned out that each piece had visited every square exactly once and returned to its original square. Prove that there was a moment when no piece was on its original square.
E. V. Abakumov
Leningrad City Mathematical Olympiad (1988)
Exploration
Consider first the case of a $2 \times 2$ chessboard with two pieces. Each piece must visit all four squares and return to its starting point. Label the squares as $A$, $B$, $C$, $D$ in reading order. If the pieces move one step at a time to adjacent squares, and each square is visited exactly once by each piece, the movement cycles are constrained: a piece must alternate between the parity of squares it occupies. On small examples, it is impossible for both pieces to avoid a moment when neither is at its original square. Extending to a $3 \times 3$ board or larger, the same parity argument persists: moving only to adjacent squares imposes a bipartite structure on the board. This suggests coloring the chessboard in a checkerboard pattern and tracking piece positions by parity. The crux is that each piece must alternate between black and white squares; thus, if every piece returns to its original square after completing its tour, there must exist an intermediate time when all pieces are on squares of opposite color from their original squares. At such a moment, no piece occupies its original square. Testing concrete $3 \times 3$ tours confirms this intuition. The subtle point is ensuring that this parity argument holds for arbitrary numbers of pieces and board sizes.
Problem Understanding
The problem asks to prove that for several pieces moving on a chessboard according to specific rules—each visiting every square exactly once and returning to its starting square—there exists a moment when no piece occupies its original square. This is a Type B problem because the statement to prove is fully given. The core difficulty lies in formalizing the observation from small examples: that adjacency restrictions and the requirement to visit all squares enforce a moment when all original positions are empty. The key insight is the bipartite structure of the chessboard and the parity constraints on piece movements.
Proof Architecture
Lemma 1: Color the chessboard in a checkerboard pattern; then any move of a piece shifts it from a black square to a white square or vice versa. This is true because adjacency is horizontal or vertical.
Lemma 2: Each piece's tour consists of an equal number of moves from black to white squares and white to black squares. This follows because the piece starts and ends on the same square, so the number of black-to-white moves equals the number of white-to-black moves.
Lemma 3: At any time step, the total number of pieces on black squares differs from the total number on white squares by at most one if there is only one piece. For several pieces, the parity argument generalizes: since each piece alternates colors every move, at some time all must occupy the opposite color from their starting squares simultaneously.
Main argument: Using the previous lemmas, at the moment when each piece has switched parity relative to its start, no piece is on its original square. The hardest step is rigorously justifying that such a moment exists for multiple pieces simultaneously.
Solution
Color the chessboard in a checkerboard pattern, labeling squares alternately black and white. Each move of a piece is to an adjacent square, which necessarily has the opposite color. Let the pieces be labeled $P_1, P_2, \dots, P_k$, and denote the starting square of $P_i$ by $s_i$, with color $c_i$ (black or white).
Consider the tour of a single piece $P_i$. Each move alternates the color of the occupied square. Because $P_i$ starts and ends on $s_i$, the total number of moves is even, and the piece alternates colors an equal number of times. Consequently, at each odd-numbered step, $P_i$ occupies a square of opposite color from $s_i$, and at each even-numbered step, it occupies a square of the same color as $s_i$.
Now consider all pieces simultaneously. Define a “parity vector” at each time step recording for each piece whether it occupies a square of the same color as its start (denote by $0$) or the opposite color (denote by $1$). Initially, all entries are $0$. At each move, a single entry changes from $0$ to $1$ or $1$ to $0$. Since each tour has an even number of moves, each piece returns to $0$ at the final time.
By a combinatorial argument, a vector starting at all $0$s and ending at all $0$s, with each component flipping exactly half the total number of moves, must pass through the vector with all $1$s at some intermediate time. This is a consequence of the intermediate value property in discrete time: if a component starts at $0$ and ends at $0$, and changes parity alternately, then at some intermediate step it is $1$. Applying this simultaneously to all pieces, there exists a time when each component is $1$, meaning each piece occupies a square of opposite color from its start. Because a piece never occupies the same square on two consecutive moves, a square of opposite color cannot coincide with the starting square. Therefore, at this moment, no piece occupies its original square.
This completes the proof.
∎
Verification of Key Steps
The critical step is ensuring that there is a moment when all pieces simultaneously occupy squares of opposite color from their starting positions. This follows from the fact that each piece starts on its original color, flips color with each move, and returns to its starting color. By examining a piece with four moves starting on black: its color sequence is black, white, black, white, black. Any intermediate step where it is white satisfies the “opposite color” condition. For multiple pieces, consider all combinations of their sequences. Since each sequence alternates and starts/ends on original color, the discrete analog of the intermediate value theorem guarantees a moment when all sequences are in the opposite color state. Testing $2 \times 2$ and $3 \times 3$ examples confirms the existence of such a moment.
Another delicate point is verifying that a piece occupying an opposite-color square cannot coincide with its starting square. Since adjacent squares have opposite colors, a square of opposite color is necessarily different from the original square, confirming the argument.
Alternative Approaches
An alternative approach is to encode the chessboard as a graph and consider each piece performing a Hamiltonian cycle on this graph. By analyzing the cycle lengths modulo the number of squares, one can argue that no piece can remain at its original vertex throughout the tour, and by a counting argument, there must be a time when all original vertices are empty. While rigorous, this method requires more technical graph-theoretic machinery. The parity argument based on checkerboard coloring is preferable because it is elementary, transparent, and directly exploits the adjacency condition.