6. What is the maximum number of knights that can be placed on a $5 \times 5$ board such that each one attacks exactly two others? (Provide an example and explain why it is not possible to place more knights.)

## 9 t h  g r a d e
6. Fig. 116 shows the arrangement of 16 knights that satisfies the problem's condition. We will show that it is impossible to place more knights. Let's color the cells of the board in black and white, as shown in Fig. 116. Note that the number of knights on black cells is equal to the number of knights on white cells. Indeed, if we connect the knights that attack each other with segments, then each segment will connect a white cell with a black one. On the other hand, from each cell, two segments emerge. Therefore, the number of segments is equal to twice the number of knights on white cells and twice the number of knights on black cells. Hence, the number of knights on white cells is equal to the number of knights on black cells.

There are 12 white cells and 13 black cells in total. If the number of empty white cells is $n$, then the number of empty black cells

![](https://cdn.mathpix.com/cropped/2024_05_21_6455f48598646f41a890g-257.jpg?height=258&width=260&top_left_y=856&top_left_x=984)

Fig. 116

![](https://cdn.mathpix.com/cropped/2024_05_21_6455f48598646f41a890g-257.jpg?height=260&width=262&top_left_y=1204&top_left_x=981)

Fig. 117 is $n+1$, and it is sufficient to prove that $n \geqslant 4$ (then at least $4+(4+1)=9$ cells are empty).

In any optimal arrangement of knights, the central cell is empty. Otherwise, out of the eight cells that the knight on the central cell attacks, exactly six are empty white cells. Hence, $n \geqslant 6$, and the number of knights does not exceed $25-6-(6+1)=12$.

Consider the cell marked with the number 1 in Fig. 117. If a knight stands on this cell, then 4 out of the 6 black cells it attacks are empty. By the proven fact, the central cell is also empty. Therefore, at least 5 black cells are empty, and the proof is complete. Therefore, we can assume that this cell is empty. Similarly, we can assume that cells 2, 3, and 4 are empty. But then $n \geqslant 4$, which is what we needed to prove.

9 c l a s s