Maths Olympiad Prep

Library / /157 of 196

Combinatorics Difficulty 5.8 AIME, harder Prove it Soviet Union

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

Solution:

Label the rows and columns of the chessboard from 11 to 88. The square in row ii and column jj is black if and only if i+ji + j is even.

Since there is one pawn in each row and column, the pawns occupy the squares (1,σ(1)),(2,σ(2)),,(8,σ(8))(1, \sigma(1)), (2, \sigma(2)), \ldots, (8, \sigma(8)) for some permutation σ\sigma of {1,2,,8}\{1,2,\ldots,8\}.

A pawn is on a black square if i+σ(i)i + \sigma(i) is even. Let BB be the number of pawns on black squares. Then
B=#{i:i+σ(i) is even}. B = \#\{i : i + \sigma(i) \text{ is even}\}.

But i+σ(i)i + \sigma(i) is even if and only if ii and σ(i)\sigma(i) have the same parity. That is, ii is odd and σ(i)\sigma(i) is odd, or ii is even and σ(i)\sigma(i) is even.

Let OO be the set of odd numbers in {1,2,,8}\{1,2,\ldots,8\}, and EE the set of even numbers. There are 44 odd and 44 even numbers. Since σ\sigma is a permutation, σ\sigma maps OO to 44 numbers, and EE to 44 numbers.

Let aa be the number of iOi \in O with σ(i)O\sigma(i) \in O, and bb the number of iEi \in E with σ(i)E\sigma(i) \in E. Then B=a+bB = a + b.

But the number of iOi \in O with σ(i)O\sigma(i) \in O is equal to the number of jOj \in O with σ1(j)O\sigma^{-1}(j) \in O, i.e., the number of odd numbers in the image of OO under σ\sigma is the same as the number of odd numbers in the preimage of OO under σ\sigma, which is aa.

Similarly, the number of iEi \in E with σ(i)E\sigma(i) \in E is bb.

But a+ba + b is the total number of ii such that ii and σ(i)\sigma(i) have the same parity. Since σ\sigma is a permutation, the number of ii with σ(i)\sigma(i) odd is 44, and the number with σ(i)\sigma(i) even is 44.

Therefore, a+ba + b is even, because aa and bb are both between 00 and 44 inclusive, and their sum is between 00 and 88 inclusive, and the only way for a+ba + b to be odd is if one is odd and one is even, but since the total number of ii is 88, and the parity is preserved, a+ba + b must be even.

Alternatively, since the total number of black squares on the board is 3232, and any arrangement of 88 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.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.