[ Chess coloring ] [ Examples and counterexamples. Constructions ]

a) What is the maximum number of bishops that can be placed on a 1000 by 1000 board so that they do not attack each other?

b) What is the maximum number of knights that can be placed on an $8 \times 8$ board so that they do not attack each other?
a) Since no more than one bishop can stand on one diagonal, and there are exactly 1999 diagonals running from the bottom-left to the top-right, and on the two outermost diagonals (each consisting of one cell) no more than one bishop can stand (they are located on the same perpendicular diagonal), no more than 1998 non-attacking bishops can be placed on the board.

This number can be achieved: for example, 1000 bishops can be placed on the top row of the board and 998 bishops on the bottom row, except for the corner cells.

b) 32 knights can be placed on all the white cells.

Divide the board into 8 rectangles of \(4 \times 2\), and each of these into four pairs of cells connected by a knight's move. In total, there are 32 pairs, and in each pair, no more than one knight can stand.

## Answer

a) 1998 bishops; b) 32 knights.