Какое наибольшее число королей можно расставить на торической шахматной доске $n\times n$, чтобы они не били друг друга? Торическая шахматная доска получается из обычной размером $n\times n$, у которой верхняя и нижняя горизонтали, а также левая и правая вертикали считаются склеенными. На торической доске с каждого поля король может пойти на восемь соседних полей (рис. 2).
Отметим на доске центры всех полей и образуем вокруг каждого короля квадрат со стороной 2 (рис. 13). Поскольку торическая доска не имеет края, квадраты эти всегда определены, и для того, чтобы короли не били друг друга, необходимо и достаточно, чтобы такие квадраты не пересекались (соприкасаться им разрешается): Для удобства сдвинем эти квадраты на полклетки вверх и вправо, чтобы их края шли по краям клетки (рис. 14). Тогда наша задача заменяется эквивалентной: какое наибольшее число $N$ квадратов $2\times2$ можно pacпoложить на торической доске $n\times n$ так, чтобы они не пересекались?
Рис. 13Рис. 14
Если $n=2m$, то ответ очевиден: $m^2$ квадратов $2\times2$ полностью закроют всю доску и $N=m^2=\dfrac{n^2}4$. Пусть теперь $n=2m+1$; тогда ясно, что в каждом ряде останется не меньше одной пустой клетки, т. е. в каждом ряду квадраты покроют не больше $2m$ клеток, а всего будет покрыто не больше $2m(2m+1)$ клеток, т. е. $N\le\dfrac{2m(2m+1)}4$. Поскольку $N$ — число целое, можно написать также, что $N\le\left[\dfrac{m(2m+1)}2\right]=\left[\dfrac{n^2-n}4\right]$.
Оказывается, что эта оценка точна: на торической доске $n\times n$ всегда можно разместить $\left[\dfrac{n^2-n}4\right]$ квадратов $2\times2$.
Укажем простейший способ такого размещения. Пусть сначала $m$ чётное, тогда $n=4k+1$, $N=\dfrac{m}2\cdot(2m+1)$. Оставим пустыми клетки, получающиеся друг из друга ходом коня в одном и том же направлении (см. рис. 15). Тогда оставшиеся клетки нетрудно закрыть квадратами, как на рисунке 16. Поставив короля в левый нижний угол каждого из квадратов, мы получим решение задачи.
Рис. 15Рис. 16Рис. 17
Пусть теперь $m$ нечётно, т. е. $n=4k+3$. Тогда $N=\left[\dfrac{n^2-n}4\right]=(k+1)(4k+1)$. Разместить это количество квадратов можно следующим способом: вписать в исходный квадрат со стороной $4k+3$ квадрат со стороной $4k+1$, оставив по краям рамочку, и заполнить его точно так, как выше, а затем плотно заполнить и рамочку, как показано на рисунке 17.
