Estonian Math Competitions

Clearly one can place only $1$ knight on an $1 \times 1$ board, which is $\lfloor \frac{1^2}{2} \rfloor$, and at most $4$ knights on an $2 \times 2$ board. In the rest, assume $n \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 \times 4$, $3 \times 4$ and $3 \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 \times 3$ and $5 \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 \times 4$, $3 \times 4$ and $3 \times 6$. Taking into account that an additional knight may be on the middle square, it also follows that there cannot be more than $\lfloor \frac{3^2}{2} \rfloor$ knights on a $3 \times 3$ board or more than $\lfloor \frac{5^2}{2} \rfloor$ knights on a $5 \times 5$ board. As a $4 \times 4$ board can be formed from two $2 \times 4$ boards and a $6 \times 6$ board from two $3 \times 6$ boards, there cannot be more than $\frac{4^2}{2}$ knights on a $4 \times 4$ board or more than $\frac{6^2}{2}$ knights on a $6 \times 6$ board.

Fig. 22

Fig. 23

Fig. 24

Fig. 25

Fig. 26

If $n \ge 7$ then an $n \times n$ board can be divided into pieces of size $4 \times 4$, $r \times 4$ and $r \times r$, where $3 \le r \le 6$ and $4 \mid n-r$. By the above, neither $4 \times 4$ nor $r \times 4$ board can contain more knights than half of the number of unit squares ($5 \times 4$ and $6 \times 4$ are divisible into rectangles of size $2 \times 4$ and $3 \times 4$). The same holds for an $r \times r$ piece, if the middle square in the case of odd $r$ is not taken into account. Thus for no $n \ge 3$ can one place more than $\lfloor \frac{n^2}{2} \rfloor$ knights on an $n \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 $\frac{n^2}{2}$ if $n$ is even. In the case of odd $n$, the number of unit squares whose color coincides with the color of the middle square is $\lfloor \frac{n^2}{2} \rfloor$. Hence one can place $\lfloor \frac{n^2}{2} \rfloor$ pairwise non-attacking knights on an $n \times n$ board.