HMMT 二月 2005 · COMB 赛 · 第 7 题

HMMT February 2005 — COMB Round — Problem 7

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

解析

What is the maximum number of bishops that can be placed on an 8 × 8 chessboard such that at most three bishops lie on any diagonal? Solution: 38 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, 4, and 2. 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 = 19 bishops on black squares. Likewise there can be at most 19 bishops on white squares for a total of at most 38 bishops. This is indeed attainable as in the diagram below. 2 X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X