1
$\begingroup$

We have arranged 8 rooks in a chess board in such a way that none captures the other. Prove that the number of black squares occupied by the rooks is even.

Doesn't it depend on how our chess board is colored? Because I want to claimthat $i+j$ is a function that gives us black or white when $i+j$ is even or odd. Is that a good idea?

$\endgroup$
5
  • $\begingroup$ Do you mean the number of black squares occupied? It seems fair to assume the usual way of colouring the board. $\endgroup$ Sep 19 '13 at 18:38
  • $\begingroup$ Yes. What is the usual way? (1,1) is black or white? $\endgroup$
    – Pejman.S
    Sep 19 '13 at 18:40
  • $\begingroup$ That should not matter, since if you can show the number of black squares is even, so must the number of white squares be. $\endgroup$ Sep 19 '13 at 18:41
  • $\begingroup$ Yes, but it differs in my function that $i+j=2k$ is black or white. No? $\endgroup$
    – Pejman.S
    Sep 19 '13 at 18:43
  • $\begingroup$ So pick one of them and mention that by symmetry, it does not matter. $\endgroup$ Sep 19 '13 at 18:44
3
$\begingroup$

If the chessboard squares are given coordinates so that (1,1) is in the lower left-hand corner when viewed from the White player's side of the board, then square (i,j) is black if $i+j \equiv 0 \pmod{2}$, and white if $i+j \equiv 1 \pmod{2}$. Let's say the rooks are on $(1,j_1), (2, j_2), \dots , (8, j_8)$. Then the parity of the number of rooks on white squares is given by

$(1+j_1) + (2 +j_2) + \dots + (8+j_8) \equiv 1+2+\dots+8 + j_1+j_2+\dots +j_8 \pmod{2}$

But the j's are a permutation of 1,2, ..., 8, so the sum is $0 \pmod{2}$. Therefore the number of rooks on white squares is even, and so must be the number of rooks on black squares, since there are 8 rooks in all.

$\endgroup$
1
  • $\begingroup$ +1 A nice argument. It is based on the congruence $i+j\equiv[\text{square $(i,j)$ is white}]\pmod2$ where the brackets mean a value $1$ if the condition holds, $0$ otherwise. The number of white squares is the sum of the bracketed expression over all occupied squares, so congruent modulo $2$ to the sum of $(i,j)$ over all occupied squares. The letter sum is always $2\binom92$ for a valid placement, so even. By the same argument, for any size board, if the lower left square is black, the number of occupied white squares is always even. $\endgroup$ Sep 20 '13 at 4:21
2
$\begingroup$

Rook placements on a chess board correspond to permutations of $8$; for instance you could agree that placing a rook on $E8$ (my favourite square, the one where the Black King starts out) means the permutation maps $5\mapsto8$, occupying $G2$ means mapping $7\mapsto 2$ and so forth. There is one black diagonal, with an even number of squares; placing rooks there is certainly valid and occupies an even number of black squares (in the given convention it corresponds to identity permutation).

It is well known that all permutations can be converted into one another by a series of (left multiplications by) transpositions; this is equivalent to saying transpositions generate the symmetric group. Now it suffices to check that performing a transposition leaves unchanged the parity of the number of occupied black squares. Applying a transposition means taking two rooks and placing them on two new squares, so that the four squares concerned form the corners of a rectangle (with sides parallel to the sides of the board). Then it will suffice to check that the number of black squares among those four corners is always even. This is easy to check by considering the $4$ possible cases for the parities of the lengths of the two sides.

$\endgroup$
2
  • $\begingroup$ I first upvoted but then I realized I hadn't understood your answer well. Why rook placements on a chess board correspond to permutations of 8? I mean why $E8$ is $5 \mapsto 8$? Isn't $G8$ simply the same as saying rook is at $(5,8)$? $\endgroup$
    – user66733
    Sep 19 '13 at 19:20
  • $\begingroup$ @some1.new4u: A permutation of $8$ means mapping $\{1,2,3,4,5,6,7,8\}$ to itself bijectively. A rook placement consists of choosing a square in each file (column) such that at the end one is chosen in each rank (row). The files are associated to the numbers at the numbers at the start (domain) of the permutation, the ranks with their images. So with file E corresponding to number 5, occupying rank 8 in that file corresponds to mapping $5\mapsto8$. Once all rooks are placed (correctly) a complete permutation of $8$ is determined. $\endgroup$ Sep 20 '13 at 4:09
1
$\begingroup$

Let's color the board differently. We color a square red if it is $(1,0) \pmod{2}$, blue if it is $(0,1) \pmod{2}$, green if it is $(1,1) \pmod{2}$ and yellow if it is $(0,0) \pmod{2}$.

Then, the number of rooks on red or green squares is 4 (number of rooks in an odd row), the number of rooks on red or yellow squares is 4 (number of rooks in an even column), so the number of green and yellow squares is even.

Hence, there are an even number of black (or white, depending on your actual coloring) squares.

This also shows you how to deal with a general $n\times n$ board, and you can trace the parity of the number of rooks on black squares.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.