Problem:
Eight pawns are placed on a chessboard, so that there is one in each row and column. Show that an even number of the pawns are on black squares.
Problem:
Eight pawns are placed on a chessboard, so that there is one in each row and column. Show that an even number of the pawns are on black squares.
Solution:
Label the rows and columns of the chessboard from to . The square in row and column is black if and only if is even.
Since there is one pawn in each row and column, the pawns occupy the squares for some permutation of .
A pawn is on a black square if is even. Let be the number of pawns on black squares. Then
But is even if and only if and have the same parity. That is, is odd and is odd, or is even and is even.
Let be the set of odd numbers in , and the set of even numbers. There are odd and even numbers. Since is a permutation, maps to numbers, and to numbers.
Let be the number of with , and the number of with . Then .
But the number of with is equal to the number of with , i.e., the number of odd numbers in the image of under is the same as the number of odd numbers in the preimage of under , which is .
Similarly, the number of with is .
But is the total number of such that and have the same parity. Since is a permutation, the number of with odd is , and the number with even is .
Therefore, is even, because and are both between and inclusive, and their sum is between and inclusive, and the only way for to be odd is if one is odd and one is even, but since the total number of is , and the parity is preserved, must be even.
Alternatively, since the total number of black squares on the board is , and any arrangement of pawns with one in each row and column must cover an even number of black squares, as shown above.
Thus, the number of pawns on black squares is even.