А шахматную доску выставляют королей трёх цветов: красного, синего и зелёного. Какое максимальное число королей можно выставить на доску 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.