Maths Olympiad Prep

Library / /9 of 13

Combinatorics Difficulty 6.4 National olympiad Find the answer

Determine the maximum number of bishops that we can place in a 8×88 \times 8 chessboard such that there are not two bishops in the same cell, and each bishop is threatened by at most one bishop.

Note: A bishop threatens another one, if both are placed in different cells, in the same diagonal. A board has as diagonals the 22 main diagonals and the ones parallel to those ones.

A number or a short expression. Spacing and $ signs are ignored.

Solution

To solve this problem, we need to determine the maximum number of bishops that can be placed on an 8×88 \times 8 chessboard such that each bishop is threatened by at most one other bishop. The key here is to understand the attacking capability of bishops on a chessboard.

Bishops move diagonally, which means they control all the squares on the diagonals they occupy. Therefore, if a bishop is placed on a particular square, it can threaten any other bishop on the same diagonal.

### Step-by-step Explanation:
1. **Diagonals on an 8×88 \times 8 board:**

- There are 1515 possible diagonals in each diagonal direction on an 8×88 \times 8 board (from the top-left to bottom-right, and from top-right to bottom-left).

2. Placing Bishops:

- We need to place the bishops such that no more than two bishops are on the same diagonal and every bishop is only threatened by at most one other bishop. That means at most two bishops can be placed on each diagonal without violating the threat constraint.

3. Strategy for Maximum Placement:

- The objective is to utilize the longer diagonals more effectively because these allow placing two bishops threatening each other.

- Specifically, for each longest diagonal, we place two bishops as they fully utilize the diagonal's length.

4. Calculation for Maximum Bishops:

- The board can be broken into two sets of diagonals—one set increasing from bottom-left to top-right and another set decreasing from top-left to bottom-right. Both sets have 1515 diagonals each.

- Since no two bishops should be on the same cell, and adding more than two bishops on any diagonal would cause more threats than allowed, we can place two bishops on several diagonals and strategically use shorter diagonals as needed.

5. Final Determination:

- To maximize, we primarily use 1010 diagonals that can accommodate two bishops each. This accounts for 2020 bishops:

2×10=20 2 \times 10 = 20

- Thus, it can be shown through examples and layouts that the maximum number of bishops we can place under the given conditions is indeed:
20 \boxed{20}
6. Conclusion:

- The placement ensures that at most one other bishop threatens any placed bishop, utilizing diagonal symmetry and bishop placement strategies effectively for maximized output.

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: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.