Олимпиадная задача по теории графов и комбинаторной геометрии для 8–10 классов
Задача
На бесконечном белом листе клетчатой бумаги конечное число клеток окрашено в чёрный цвет так, что у каждой чёрной клетки чётное число (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 – соседи по диагонали, то при каждом перекрашивании они находились либо обе внутри многоугольника, либо обе – вне, и значит одна из них зелёная, другая – красная, как это было вначале.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь