Eight pieces are placed on a chessboard so that each row and each column contains exactly one piece. Prove that there are an even number of pieces on the black squares of the board.
Problem
Source:
Tags: combinatorics
02.09.2023 16:18
02.09.2023 16:56
An easier argument: The solutions correspond to the permutations $\sigma\in S_8$ where the pieces are placed in position $(n,\sigma(n))$ for $1\leq n\leq 8$. Note that if we move the two pieces at $(i,\sigma(i))$ and $(j,\sigma(j))$ to positions $(j,\sigma(i))$ and $(i,\sigma(j))$ then the parity of the numbers of pieces on the white squares as well as on the black squares is preserved. Indeed if these two pieces were on both on the same color space, then they will still be after this move, and if they were on opposite colored spaces, they will still be after this move. But this corresponds to changing to a permutation $\tau$ that differs from $\sigma$ by a transposition. Since every permutation is a product of transpositions and the for identity permutation has all eight pieces on the same color space as the top-left color, we are done.
02.09.2023 18:00
Brilliant solution, rchokler. It’s always a pleasure to read your solutions and to work through them.