Olympiad Maths Prep

Track / Stage 6 / 184 of 400 #1184 of 2000

Problem 1184

National olympiad, first round
Combinatorics Difficulty 6.3 Find the answer

On a chessboard 8×88\times 8, n>6n>6 Knights are placed so that for any 6 Knights there are two Knights that attack each other. Find the greatest possible value of nn.

Official solution

1. Understanding the Problem:
We need to place n n knights on an 8×8 8 \times 8 chessboard such that for any 6 knights, there are at least two knights that attack each other. We aim to find the maximum value of n n .

2. Initial Construction:
Consider placing knights on the board in a specific pattern. One effective way is to place knights on squares of the same color in a checkerboard pattern. This ensures that any two knights on the same color squares will attack each other if they are within the knight's move range.

3. Checkerboard Pattern:
On an 8×8 8 \times 8 chessboard, there are 32 squares of each color (black and white). If we place knights on squares of the same color, we can place up to 32 knights. However, we need to ensure that for any 6 knights, at least two attack each other.

4. Placing Knights:
Let's place knights on every second square of the same color. This means placing knights on either all black squares or all white squares. This gives us 32 knights, but we need to check if this satisfies the condition.

5. Verification:
If we place knights on all squares of one color, any 6 knights chosen will always have at least two knights that attack each other because they are on the same color and within the knight's move range.

6. **Maximizing n n :**
To find the maximum n n , we need to ensure that placing more than 10 knights will still satisfy the condition. Let's consider placing 10 knights in a specific pattern:
- Place knights on the following coordinates: (1,1), (1,3), (1,5), (1,7), (3,1), (3,3), (3,5), (3,7), (5,1), (5,3). This ensures that any 6 knights chosen will have at least two knights attacking each other.

7. Proof by Contradiction:
Assume we can place more than 10 knights such that no two knights attack each other for any 6 knights chosen. This leads to a contradiction because:
- If we place an 11th knight, it must attack at least one of the existing knights due to the limited number of squares and the knight's move range.
- Therefore, placing more than 10 knights will always result in at least two knights attacking each other for any 6 knights chosen.

8. Conclusion:
The maximum number of knights that can be placed on an 8×8 8 \times 8 chessboard such that for any 6 knights, at least two attack each other is 10.

The final answer is 10\boxed{10}.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.