|
|
 |
Условие
Каждая клетка шахматной доски закрашена в один из цветов – синий или красный. Докажите, что клетки одного из цветов обладают тем свойством, что их может обойти шахматный ферзь (на клетках этого цвета ферзь может побывать не один раз, на клетки другого цвета он не ставится, но может через них перепрыгивать).
Решение 1
Если на доске найдётся одноцветная строка или столбец, то утверждение очевидно. Иначе будем действовать следующим образом: обойдём все красные клетки первой горизонтали, перейдём на вторую, там тоже обойдём все красные клетки и т.д. Пусть мы не смогли перейти с i-й горизонтали на (i+1)-ю. Тогда начнём обходить все синие клетки последовательно, начиная с первой вертикали. Пусть мы не смогли перейти с j-й вертикали на (j+1)-ю. Пусть
(i, j) – красная клетка, тогда (i + 1, j) и (i + 1, j + 1) – синие. Но тогда можно перейти с синей клетки (i + 1, j) на j-й вертикали на синюю клетку
(i + 1, j + 1) на (j+1)-й вертикали. Противоречие.
Аналогично приходим к противоречию и в случае, когда клетка (i, j) – синяя.
Решение 2
Назовём такой цвет связным. Докажем утверждение для прямоугольной доски индукцией по числу столбцов.
База: для одного столбца оба цвета связны.
Шаг индукции. Выделим из доски левый столбец. По предположению индукции на оставшейся части один из цветов (пусть синий) связен. Рассмотрим множество P клеток левого столбца, куда проектируются синие клетки остальных столбцов. Если одна из клеток P синяя, то синий цвет связен.
Пусть все клетки P – красные. Рассмотрим красные горизонтали правой части (если их нет, весь левый столбец – красный, и кpасный цвет связен). Выберем ту из них, которая граничит с горизонталью, где есть синие клетки. С выбранной горизонтали можно перейти на клетку P. Значит, красный цвет связен.
Замечания
9 баллов
