Задача: на 6x6 доске расставляют королей трех цветов (красного, синего, зелёного). Короли одного цвета не должны бить друг друга. Короли разных цветов могут бить друг друга. Найдите максимальное число королей.
Ключевые идеи:
- В каждой 2x2 клетке любые две клетки являются соседними для короля (они бьют друг друга). Значит в любой 2x2 блок можно поставить не более 3 королей (если поставить все 4, две короля одного цвета обязательно будут бить друг друга).
- Доску можно разбить на 9 независимых 2x2 блоков. Тогда сверху-слово: максимум королей ≤ 9 блоков × 3 короля в каждом = 27.
Как достичь 27:
Разделим доску на те же 9 блоков 2x2 и в каждом блоке разместим три короля разного цвета так:
- красный (R) стоит в верхнем левом углу блока,
- синий (B) — в верхнем правом,
- зелёный (G) — в нижнем левом,
- нижний правый угол блока остаётся пустым.
Пусть блоки пронумерованы по строкам и столбцам (i, j), где i, j = 1, 2, 3. Тогда координаты расположения королей внутри блока (2i−1, 2j−1) — красный, (2i−1, 2j) — синий, (2i, 2j−1) — зелёный. Это повторяется во всех блоках.
Проверка на отсутствие боёв одинаковых цветов:
- Красные короли расположены на клетках с обоими координатами нечетными: (odd, odd). Любая соседняя клетка будет иметь хотя бы одну координату чётной, значит не может быть красной. Таким образом красные короли не бьют друг друга.
- Аналогично синие стоят на (odd, even), зелёные — на (even, odd). Для любых двух таких клеток различия по любой координате по модулю равны 0 или 2, то есть не равно 1. Следовательно, ни синий, ни зелёный король не бьют друг друга.
Следовательно, такая расстановка даёт 3 короля в каждом из 9 блоков, всего 27 королей, и ни у кого из трёх цветов нет боёв внутри своего цвета.
Ответ: 27
