Competition problem — Combinatorics

Library / /80 of 105

Combinatorics Difficulty 5.3 AIME, harder Prove it United States

Problem:

Consider an $8 \times 8$ chessboard, on which we place some bishops in the 64 squares. Two bishops are said to attack each other if they lie on a common diagonal.

a. Prove that we can place 14 bishops in such a way that no two attack each other.

b. Prove that we cannot do so with 15 bishops.

Solution

Solution:

For the first part, here is one maximal arrangement, where the location of the bishops are indicated by the letter $B$ .

$B$
$B$							$B$
$B$							$B$
$B$							$B$
$B$							$B$
$B$							$B$
$B$							$B$
$B$

To see that there cannot be 15 bishops, observe that we have highlighted 15 right-down diagonals in the square above. Each diagonal can accommodate at most one bishop. Furthermore, the lower-left corner and the upper-right corner constitute diagonals of size 1 which cannot be both occupied. This gives the bound of 14 bishops.

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.