Maths Olympiad Prep

Library / /17 of 133

, 2015

Combinatorics Difficulty 4.9 AIME Prove it Saudi Arabia

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

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 diagonals 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.

Figure 1

Conversely, if we place 3838 bishops on the four boundaries of the table and on the second and seventh rows except the second and seventh square of the second row, as shown in the picture, one can check that this arrangement satisfies the condition of the problem.

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 and solution reproduced as published; topic and difficulty added by this site.