|
|
 |
Условие
На каждую клетку доски 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 могут быть устроены по-разному. Один из вариантов изображён на рисунке (длинные стрелки означают, что несколько сторожей подряд смотрят в одну сторону, сторожа в центре могут смотреть в любую сторону).
Ответ
5
