Two rooks on a chessboard are said to be attacking each other if they are placed in the same row or column of the board. (a) There are eight rooks on a chessboard, none of them attacks any other. Prove that there is an even number of rooks on black fields. (b) How many ways can eight mutually non-attacking rooks be placed on the 9 £ 9 chessboard so that all eight rooks are on squares of the same color.
Problem
Source: MOP 2005 Homework - Red Group #8
Tags: geometry, rectangle, pigeonhole principle, rotation, combinatorics unsolved, combinatorics
08.05.2014 16:42
09.05.2014 09:22
Alternate solution for a: Count the rows from the bottom as row $1$ to the top as row $8$, and count the columns from the left as column $1$ to the right as column $8$. Denote the value of a square on row $r$ and column $c$ as $r+c$. Note that a square is black if and only if its value is even. Sum the values of all squares occupied by the rooks. Clearly, as there is one rook in each row and column, the sum will be equal to $(1+2+\cdots+8) + (1+2+\cdots+8)$ for counting the rows and counting the columns, an even number. If there are an odd number of black squares, then there are an odd number of white squares, which means the sum of the values would be odd, contradiction, so there are an even number of black squares. b: Suppose the corners are black. We divide into two cases: Case 1: The rooks are on black squares. Then we can consider the $5 \times 5$ square of black squares containing the corners and the $4 \times 4$ square of black squares not containing the corners as separate. Note that as the 8 rooks occupy 8 rows and 8 columns, there are one free row and one free column, where their intersection is not attacked or occupied by any rook. Introduce a phantom rook that will occupy the remaining free square. By using a similar argument as a, we can see that the number of rooks on the white squares must be even. Since all real rooks are on black squares, the phantom rook must be on a black square too, and thus each rook is on either the larger $5 \times 5$ square or the smaller $4 \times 4$ square. There are $5!$ ways to arrange the rooks in the larger square (for each row, choose the column that the rook in the row lies on; no two columns chosen may be the same, so this is a permutation of the columns). There are $4!$ ways to arrange the rooks in the smaller square. There are $9$ ways to choose the phantom rook, which we will remove afterwards. So in total there are $5! \cdot 4! \cdot 9$ ways to put the rooks. Case 2: The rooks are on white squares. Similar like in Case 1, we can divide the white squares into a $4 \times 5$ rectangle (with 4 rows and 5 columns) and a $5 \times 4$ (with 5 rows and 4 columns) rectangle. Clearly we cannot fit more than 4 rooks into a $4 \times 5$ rectangle as by Pigeonhole Principle two rooks will be on the same row, so there are 4 rooks in each rectangle. Now the $5 \times 4$ case is just the $4 \times 5$ case rotated, so we'll just do $4 \times 5$ and square the result. There are 4 rows and 5 columns. Each row has a rook. Thus there are $5 \times 4 \times 3 \times 2$ ways to choose which column each rook goes, making sure no column is repeated. Thus there are $5!$ ways to choose a rectangle, and so $(5!)^2$ ways if the rooks are on white squares. Summing together yields $\boxed{5! \cdot 4! \cdot 14 = 8!}$ as the final answer.