Magic Knights#13

Magic Knights (Editorial)

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