Maths Olympiad Prep

Library / /204 of 377

Combinatorics Difficulty 5.1 AIME, harder Prove it United States

Problem:
What is the maximum number of bishops that can be placed on an 8×88 \times 8 chessboard such that at most three bishops lie on any diagonal?

Solution

Solution:
If the chessboard is colored black and white as usual, then any diagonal is a solid color, so we may consider bishops on black and white squares separately. In one direction, the lengths of the black diagonals are 2,4,6,8,6,42, 4, 6, 8, 6, 4, and 22. Each of these can have at most three bishops, except the first and last which can have at most two, giving a total of at most 2+3+3+3+3+3+2=192+3+3+3+3+3+2=19 bishops on black squares. Likewise there can be at most 1919 bishops on white squares for a total of at most 3838 bishops. This is indeed attainable as in the diagram below.
Figure 1

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.