Maths Olympiad Prep

Library / /18 of 24

Combinatorics Difficulty 5.7 AIME, harder Prove it United States

Problem:

Some bishops and knights are placed on an infinite chessboard, where each square has side length 11 unit. Suppose that the following conditions hold:
- For each bishop, there exists a knight on the same diagonal as that bishop (there may be another piece between the bishop and the knight).
- For each knight, there exists a bishop that is exactly 5\sqrt{5} units away from it.
- If any piece is removed from the board, then at least one of the two conditions above is no longer satisfied.
If nn is the total number of pieces on the board, find all possible values of nn.

Solution

Solution:

Color the chessboard with the usual chessboard coloring. Note that bishops can only attack knights on the same colored squares, while knights can only attack bishops on different colored squares. Let BB,WB,BN,WNB_{B}, W_{B}, B_{N}, W_{N} denote the number of bishops on black colored squares, bishops on white colored squares, knights on black colored squares and knights on white colored squares respectively.

Since removing a knight on a white colored square will cause a leave a bishop on a white colored square with no knight to attack, WNWBW_{N} \leq W_{B}. Similarly, BNBB,BBWN,WBBNB_{N} \leq B_{B}, B_{B} \leq W_{N}, W_{B} \leq B_{N}. Combining the inequalities, we find that WN=WB=BN=BBW_{N}=W_{B}=B_{N}=B_{B}. Hence 4n4 \mid n.

To construct n=4n=4, we can place bishops at (1,0),(2,2)(1,0),(2,2) and knights at (0,1),(3,1)(0,1),(3,1). We can easily extend this to any multiple of 44 by placing this configuration as many times as required across the grid, making sure that we avoid the (finitely many) diagonals that existing bishops occupy.

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.