|
|
 |
Условие
На бесконечном белом листе клетчатой бумаги конечное число клеток окрашено в чёрный цвет так, что у каждой чёрной клетки чётное число (0, 2 или 4) белых клеток, соседних с ней по стороне. Докажите, что каждую белую клетку можно окрасить в красный или зелёный цвет так, чтобы у каждой чёрной клетки стало поровну красных и зелёных клеток, соседних с ней по стороне.
Решение
Введём координаты так, чтобы центры клеток были целочисленными, и
будем считать, что окрашены не клетки, а их центры. Вначале окрасим все белые точки в полоску: все точки с чётной абсциссой – в зелёный цвет, а все точки с нечётной абсциссой – в красный. Пусть граф Г имеет в качестве вершин множество всех чёрных точек, а в качестве рёбер – множество всех отрезков, соединяющих соседние чёрные точки. Заметим, что степень каждой вершины этого графа чётна.
Начнём движение по рёбрам из какой-то вершины. Войдя в вершину по некоторому ребру, мы сможем выйти по другому ребру, поэтому когда-нибудь придём в вершину, в которой уже были.
Тем самым, в графе найден простой цикл C. Ребра C ограничивают на плоскости многоугольник. Изменим цвет у всех красных и зелёных
точек, лежащих внутри цикла C.
Далее, перейдём к рассмотрению графа Г', получаемого из Г удалением всех рёбер цикла C. В графе Г' степень каждой вершины чётна, поэтому снова найдём простой цикл, произведём перекрашивание, удалим рёбра цикла, и т.д.
Действуем так до тех пор, пока в соответствующем графе есть рёбра.
Докажем, что полученная в конце этого процесса раскраска удовлетворяет условию.
Если у чёрной точки P четыре белых соседа, то при каждом перекрашивании они находились либо все внутри многоугольника, либо все – вне, а значит, перекрашивались одинаковое число раз. Тогда у P по два
красных и зелёных соседа, поскольку так было в начальной раскраске.
Пусть у чёрной точки P два белых соседа K и L и два чёрных соседа M и N.
Пусть K и L лежат в одной горизонтали или в одной вертикали. Тогда K и L находились в разных частях плоскости относительно цикла только при перекрашивании точек внутри цикла, содержащего путь MPN . Таким образом, количество перекрашиваний точек K и L отличается на 1. Так как в начальной раскраске K и L
одноцветны, то в конечной – разноцветны.
Если же K и L – соседи по диагонали, то при каждом перекрашивании они находились либо обе внутри многоугольника, либо обе –
вне, и значит одна из них зелёная, другая – красная, как это было вначале.
Замечания
Идея решения. Если соединить центры соседних чёрных клеток отрезками, то объединение проведённых отрезков разбивает плоскость на области. Из чётности степеней вершин следует, что области можно покрасить в два цвета (жёлтый и синий) так, чтобы области, граничащие по отрезку, имели разные цвета. Далее, покрасим зелёным в синих областях клетки с чётной абсциссой, а в жёлтых – с нечётной. Остальные клетки покрасим красным.
