На шахматную доску выставляют И зелёного. Какое королей трёх цветов: красного, синего максимальное число королей можно выставить на доску 10х10, чтобы короли одного цвета не били друг друга?

Ответ: 75 королей (25 красных, 25 синих и 25 зелёных). Пошаговое решение 1) Вводные понятия - На доске 10×10 перемещениямиKing’а можно атаковать соседние клетки по горизонтали, вертикали и диагонали. - Короли одного цвета не должны бить друг друга, значит короли одного цвета образуют независимое множество в графе, где рёбра соединяют соседние клетки. 2) Верхняя граница - Разобьём доску на 2×2 блоки. Всего таких блоков 25. - В любом 2×2 блоке любые две клетки из-за правила короля атакуют друг друга (они находятся на расстоянии не более одного по максимальной норме). Значит в одном блоке на одном и том же цвете не может быть более чем одной королём. - Следовательно, в каждом блоке по каждому цвету можно разместить не более одной фигуры. Так как цветов три, общее число королей не может превысить 3×25 = 75. - Значит максимальное возможное число королей трёх цветов не более 75. 3) Достижимость 75 - Разделим доску по паритету координат. Пусть клетки нумеруются row i и column j (i, j от 1 до 10). - Разобьем клетки на четыре цветовых класса по паритету: - Красный (R): i чётно и j чётно (i = even, j = even) - Синий (B): i чётно и j нечётно (i = even, j = odd) - Зелёный (G): i нечётно и j чётно (i = odd, j = even) - Прочее оставим пустым: i нечётно и j нечётно (i = odd, j = odd) - В каждом из трёх используемых классов ровно по 25 клеток. Короли в одном и том же цвете не бьют друг друга, потому что любые две клетки одного класса имеют как минимум расстояние по одной из координат равное 2, т.е. Chebyshev дистанция между любыми двумя клетками одного класса не меньше 2. 4) Конструкция - Разместим красных королей на всех клетках с чётными i и чётными j. - размещаем синих королей на всех клетках с чётными i и нечётными j. - размещаем зелёных королей на всех клетках с нечётными i и чётными j. - пустыми оставляем клетки с нечётными i и нечётными j. Такой расклад даёт: - 25 красных, 25 синих и 25 зелёных королей. - В каждой цветовой группе короли не бьют друг друга. - Нежелательные ограничения по другим цветам не мешают, так как требование касается только королей одного цвета. Итого, максимальное число королей трёх цветов на доске 10×10 равно 75.