First key fact:
Knights always attack cells of the opposite color to the one they are on.
Second key fact:
For n\ne2, it is advantageous to place all the knights on cells of the same color.
To obtain the maximum number of knights that we can place on one board for n \ne 2, let's calculate the number of cells of each color:
Black cells: \lfloor \frac{n^2}{2} \rfloor
White cells: \lceil \frac{n^2}{2} \rceil
When , we can place knights on all n^2 cells, because no knight can reach another.
Now, having the maximum number of knights, , that we can place on one board, the number of boards needed to accommodate knights is found by the formula:
re=\lceil \frac{K}{max} \rceil
Asymptotic complexity:
Problem Author: | Bohdan Feisa |
Problem Prepared by: | Bohdan Feisa, Pavlo Tsikey |
Editorial by: | Bohdan Feisa |