Олимпиадная задача: Максимум сторожей в $8 \times 8$ площади

Докажем, что $k\le 5$. Для этого предположим, что $k \geq 6$. Рассмотрим сторожей, стоящих в углах доски. На каждого из них смотрят по крайней мере $6$ сторожей, и эти сторожа должны стоять у края доски. При этом, если какой-то сторож видит одного из угловых сторожей, то он не видит других угловых сторожей. Таким образом, хотя бы $24$ сторожа, стоящих у края доски, смотрят вдоль сторон доски. Тогда «внутрь» доски, не на угловых сторожей, смотрит не более четырёх сторожей, стоящих у границ.

Рассмотрим теперь сторожей, стоящих в центральном квадрате $6\times 6$. Посчитаем для них максимально возможное количество «входящих взглядов». (Взгляды, обращённые на сторожей на границе доски, подсчитывать не будем.) Это число не превосходит $184=24+100+48+12$. (В этой сумме $24$ — от четырёх сторожей на границе, $100$ — по $5$ взглядов от каждого из $20$ сторожей на границе квадрата $6\times 6$, $48$ — по $4$ взгляда от каждого из $12$ сторожей на границе квадрата $4\times 4$, $12$ — по $3$ взгляда от каждого из $4$ сторожей из центрального квадрата $2\times 2$.) Таким образом, на $36$ сторожей приходится $184=36\cdot 5+4 < 36\cdot 6$ взглядов. Значит, среди сторожей есть те, которым досталось меньше $6$ взглядов.

Примеры для $k=5$ могут быть устроены по-разному. Один из вариантов изображён на рисунке (длинные стрелки означают, что несколько сторожей подряд смотрят в одну сторону, сторожа в центре могут смотреть в любую сторону).