|
|
 |
Условие
На каждую клетку доски $8 \times 8$ поставили по сторожу. Каждый сторож может смотреть в одном из четырёх направлений (вдоль линий доски) и сторожить всех сторожей на линии своего взгляда. Для какого наибольшего $k$ можно так направить взгляды сторожей, чтобы каждого сторожа сторожили не менее $k$ других сторожей?Решение
Докажем, что $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$ могут быть устроены по-разному. Один из вариантов изображён на рисунке (длинные стрелки означают, что несколько сторожей подряд смотрят в одну сторону, сторожа в центре могут смотреть в любую сторону).
