Maths Olympiad Prep

Library / /77 of 86

Combinatorics Difficulty 7.0 National olympiad Prove it Estonia

Let nn be a positive integer. Find the largest number of knights that can be placed on a board of size n×nn \times n in such a way that no two knights attack each other. A knight attacks precisely the squares that are located either horizontally by one square and vertically by two squares away or horizontally by two squares and vertically by one square away.

Figure 1

Solution

Clearly one can place only 11 knight on an 1×11 \times 1 board, which is 122\lfloor \frac{1^2}{2} \rfloor, and at most 44 knights on an 2×22 \times 2 board. In the rest, assume n3n \ge 3.

If a set of unit squares is divided into pairs in such a way that a knight on one square of any pair attacks the other square of that pair then there cannot be more knights than half of the total number of unit squares in this set without some knights attacking each other. In Figures 22, 23 and 24, all unit squares of boards of size 2×42 \times 4, 3×43 \times 4 and 3×63 \times 6 are divided into pairs whose members are located at one knight move from each other. In Figures 25 and 26, all unit squares of boards of size 3×33 \times 3 and 5×55 \times 5 except the middle square are divided into pairs whose members are located at one knight move from each other. By the above, it is impossible to place knights to more than half of unit squares of boards of size 2×42 \times 4, 3×43 \times 4 and 3×63 \times 6. Taking into account that an additional knight may be on the middle square, it also follows that there cannot be more than 322\lfloor \frac{3^2}{2} \rfloor knights on a 3×33 \times 3 board or more than 522\lfloor \frac{5^2}{2} \rfloor knights on a 5×55 \times 5 board. As a 4×44 \times 4 board can be formed from two 2×42 \times 4 boards and a 6×66 \times 6 board from two 3×63 \times 6 boards, there cannot be more than 422\frac{4^2}{2} knights on a 4×44 \times 4 board or more than 622\frac{6^2}{2} knights on a 6×66 \times 6 board.

Figure 2
Fig. 22
Figure 3
Fig. 23
Figure 4
Fig. 24
Figure 5
Fig. 25
Figure 6
Fig. 26

If n7n \ge 7 then an n×nn \times n board can be divided into pieces of size 4×44 \times 4, r×4r \times 4 and r×rr \times r, where 3r63 \le r \le 6 and 4nr4 \mid n-r. By the above, neither 4×44 \times 4 nor r×4r \times 4 board can contain more knights than half of the number of unit squares (5×45 \times 4 and 6×46 \times 4 are divisible into rectangles of size 2×42 \times 4 and 3×43 \times 4). The same holds for an r×rr \times r piece, if the middle square in the case of odd rr is not taken into account. Thus for no n3n \ge 3 can one place more than n22\lfloor \frac{n^2}{2} \rfloor knights on an n×nn \times n board.

On the other hand, coloring the unit squares black and white chesswise, one can place a knight on all squares of one and the same color since a knight attacks only squares of the opposite color. The number of unit squares of a fixed color is n22\frac{n^2}{2} if nn is even. In the case of odd nn, the number of unit squares whose color coincides with the color of the middle square is n22\lfloor \frac{n^2}{2} \rfloor. Hence one can place n22\lfloor \frac{n^2}{2} \rfloor pairwise non-attacking knights on an n×nn \times n board.

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.