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

Ответ: 75 королей.

Пошаговое объяснение

• Правило задачки: короли одного цвета не должны бить друг друга. Значит, если в одной и той же 2x2 клетке стоят короли одного цвета, они обязательно будут бить друг друга, потому что любая пара клеток в 2x2 блоке соседняя.
• В любой 2x2 клетке можно разместить не более 3 королей (если расставить все 4, по pigeonhole два короля будут одного цвета и будут бить друг друга).
• Доску 10x10 можно разбить на 25 неперекрывающих друг друга блоков 2x2. Следовательно, максимальное теоретическое число королей не может превышать 25×3 = 75.

Достижимо ли 75?

• Да. Одно частное решение: возьмём стандартную 4-цветовую раскраску по клеткам с периодикой 2x2: в каждом 2x2 блоке цвета расставляются так: A B C D Где A,B,C,D — четыре разных цвета.
• Если мы удалим цвет D со всей доски и оставим только три цвета A,B,C, то никакие две клетки одного цвета не будут соседними (в 2x2 блоке все соседние клетки имеют разные цвета, а мы просто исключили D). Значит, короли одного цвета не будут бить друг друга, а можно разместить королей трёх цветов по оставшимся клеткам.

Конкретное удобное описание размещения

• Нумеруем клетки по координатам (i, j), i и j от 1 до 10.
• Помещайте короля на все клетки, у которых не оба координаты являются нечетными (то есть не на клетках типа (1,1), (1,3), …, (9,9)).
• Это оставляет 100 − 25 = 75 клеток для размещения королей.
• Эти клетки можно окрасить тремя цветами (к примеру, по той же паритетной раскраске: пары (четный,четный), (четный,нечетный), (нечетный,четный) соответствуют трем цветам). Любые две соседние клетки будут иметь разные цвета, и поэтому короли одного цвета не будут бить друг друга.

Итого: максимум королей, которых можно разместить, не нарушив условие (для красного, синего и зелёного) на доске 10×10, равен 75.