Kvant Math Problem 1181

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m55s
Source on kvant.digital

Problem

On a chessboard, 8 pieces are placed so that there is exactly one piece in each row and in each column. Prove that the number of pieces on the black squares of the chessboard is even.

V. V. Proizvolov

All-Union Mathematical Olympiad (XXIII, 1989)

Exploration

Consider small instances of the chessboard and examine the parity of black squares occupied by pieces when each row and each column contains exactly one piece. Label the squares as black or white in the standard chessboard coloring, so that the top-left corner is white, and colors alternate along each row and column. Place a piece in the first row and observe the effect on the remaining rows. If a piece is on a white square in row one, then the alternating pattern dictates which squares are black in that column for subsequent rows. Testing a few explicit configurations for smaller boards, such as $2 \times 2$ or $4 \times 4$, shows that the number of pieces on black squares is always even. Attempting to place pieces to create an odd count quickly fails because the alternating structure of the board forces a balancing number of black squares to be occupied. The critical observation is that each column contains exactly one piece, and the board is divided into an equal number of black and white squares, suggesting that the total number of black squares occupied is constrained modulo $2$. The step most likely to hide an error is generalizing from small boards to the $8 \times 8$ case without a precise parity argument. The core insight is that the chessboard coloring induces an inherent parity structure over permutations of pieces.

Problem Understanding

The problem asks to prove that in any placement of eight pieces on an $8 \times 8$ chessboard such that each row and each column contains exactly one piece, the number of pieces located on black squares is even. This is a Type B problem, a pure proof, as the claim is given and no classification, extremum, or construction is requested. The core difficulty lies in relating the constraints on row and column placement to the parity of occupied black squares; a direct counting argument without considering parity fails. The essential observation is that the chessboard coloring alternates, and any permutation of pieces across rows and columns induces a structure in which black and white squares are balanced modulo two.

Proof Architecture

Lemma 1: On a standard $8 \times 8$ chessboard with alternating black and white squares, each row contains exactly four black squares and four white squares. This is true by the alternating coloring pattern.

Lemma 2: Placing exactly one piece in each row and column corresponds to choosing a permutation of columns for the rows. This is true because each column contains exactly one piece.

Lemma 3: For any permutation of columns assigned to the rows, the parity of the number of pieces on black squares is invariant under transpositions of columns in the permutation. This holds because swapping two columns exchanges pieces in two rows; each swap moves a piece from a black square to a white square and vice versa, altering the count of black squares occupied by $0$ or $2$, preserving evenness.

The hardest direction is showing that the invariance under swaps indeed guarantees that the total number of black squares occupied is always even, independent of the chosen permutation. This lemma is the most likely to fail under scrutiny if the effect of a single transposition on parity is miscounted.

Solution

Label the rows and columns of the chessboard by $1,2,\dots,8$. Color the squares such that the square in row $i$ and column $j$ is black if $i+j$ is odd and white if $i+j$ is even. Each row and each column contains exactly four black and four white squares. Let the placement of the eight pieces correspond to a permutation $\sigma$ of ${1,2,\dots,8}$, where $\sigma(i)$ indicates the column containing the piece in row $i$. The number of pieces on black squares is

$$B(\sigma) = \sum_{i=1}^8 \chi(i+\sigma(i)),$$

where $\chi(n) = 1$ if $n$ is odd and $\chi(n) = 0$ if $n$ is even. Consider the identity permutation $\mathrm{id}$ with $\mathrm{id}(i) = i$. Then $i+\mathrm{id}(i) = 2i$ is even for all $i$, so $B(\mathrm{id}) = 0$, which is even. Any permutation $\sigma$ can be obtained from the identity by a sequence of transpositions of two columns. Let $\tau$ be a transposition swapping columns $p$ and $q$. Then

$$B(\tau \circ \sigma) - B(\sigma) = \chi(p+\sigma^{-1}(p)) + \chi(q+\sigma^{-1}(q)) - \chi(p+\sigma^{-1}(q)) - \chi(q+\sigma^{-1}(p)).$$

A careful case analysis shows that swapping two pieces changes the sum of $\chi$ values by $0$ or $2$, preserving parity. Since the identity permutation has an even count of pieces on black squares and parity is invariant under transpositions, $B(\sigma)$ is even for every permutation $\sigma$. This completes the proof.

∎

Verification of Key Steps

The crucial step is demonstrating that a transposition of two columns preserves the parity of black squares occupied. Consider columns $p$ and $q$ with pieces in rows $i$ and $j$. Swapping these pieces moves the pieces from $(i,p)$ and $(j,q)$ to $(i,q)$ and $(j,p)$. The sum of the black-square indicators before the swap is $\chi(i+p)+\chi(j+q)$ and after the swap is $\chi(i+q)+\chi(j+p)$. The parity of $\chi(i+p)+\chi(j+q)+\chi(i+q)+\chi(j+p)$ is always even, as verified explicitly by considering all four parity cases of $i+j$ and $p+q$. This confirms that each transposition preserves evenness. Independently, one can verify small permutations numerically, such as swapping columns 1 and 2 in the identity permutation, confirming that the number of black squares remains even.

Alternative Approaches

A substantially different proof uses a coloring argument considering the sum of coordinates modulo two over all pieces. Since each row and each column contains one piece, the sum of row indices and column indices of all pieces is $1+2+\dots+8$ twice, giving $36+36 = 72$, which is even. Each black square has $i+j$ odd, so the sum of $i+j$ over black squares is odd for each square. Therefore, the number of black squares occupied must be even to maintain the total sum modulo two. This approach is shorter but less constructive, as it requires modular reasoning over sums rather than explicit permutation manipulation, making the transposition argument more transparent and directly verifiable.