Разделы 
Дополнительно
Задача по математике - 2043
2019-01-23 
На бесконечном белом листе клетчатой бумаги конечное число клеток окрашено в черный цвет так, что у каждой черной клетки четное число (0, 2 или 4) белых клеток, соседних с ней по стороне. Докажите, что каждую белую клетку можно покрасить в красный или зеленый цвет так, чтобы у каждой черной клетки стало поровну красных и зеленых клеток, соседних с ней по стороне.
Решение:
Идея решения состоит в следующем. Если соединить центры соседних черных клеток отрезками, то объединение проведенных отрезков разбивает плоскость на области. Из четности степеней вершин следует, что области можно покрасить в два цвета (желтый и синий) так, чтобы области, граничащие по отрезку, имели разные цвета. Далее, покрасим зеленым в синих областях клетки с четной абсциссой, а в желтых - с нечетной. Остальные клетки покрасим красным.
Проведем формальные рассуждения. Введем координаты так, чтобы центры клеток были целочисленными, и будем считать, что окрашены не клетки, а их центры. Вначале окрасим все белые точки «в полоску», т. е. так, чтобы зеленые точки имели четную абсциссу, а красные - нечетную. Пусть граф $Г$ имеет в качестве вершин множество $V$ всех черных точек, а в качестве ребер - множество всех отрезков $E$, соединяющих соседние черные точки. Заметим, что степень каждой вершины в $Г$ четна.
Начнем движение по ребрам из какой-то вершины. Войдя в вершину по некоторому ребру, мы сможем выйти по другому ребру, поэтому когда- нибудь придем в вершину, в которой уже были. Тем самым, в графе найден простой цикл $C$. Ребра $C$ ограничивают на плоскости многоугольник. Изменим цвет у всех красных и зеленых точек, лежащих внутри цикла $C$. Далее, перейдем к рассмотрению графа $Г^{\prime}$, получаемого из $Г$ удалением всех ребер цикла $C$. В графе $Г^{\prime}$ степень каждой вершины четна, поэтому снова найдем простой цикл, произведем перекрашивание, удалим ребра цикла, и т. д. Действуем так до тех пор, пока в соответствующем графе есть ребра.
Докажем, что полученная в конце этого процесса раскраска удовлетворяет условию.
Если у черной точки $P$ четыре белых соседа, то при каждом перекрашивании они находились либо все внутри многоугольника, либо все - вне, а значит перекрашивались одинаковое число раз. Тогда у $P$ по два красных и зеленых соседа, поскольку так было в начальной раскраске.
Пусть у черной точки $P$ два белых соседа $K$ и $L$, и два черных соседа $M$ и $N$.
Пусть $K$ и $L$ лежат в одной горизонтали или в одной вертикали. Тогда $K$ и $L$ находились в разных частях плоскости относительно цикла только при перекрашивании точек внутри цикла, содержащего путь $MPN$. Таким образом, количество перекрашиваний точек $K$ и $L$ отличается на 1. Так как в начальной раскраске $K$ и $L$ одноцветны, то в конечной - разноцветны.
Если же $K$ и $L$ - соседи по диагонали, то при каждом перекрашивании они находились либо обе внутри многоугольника, либо обе - вне, и значит одна из них зеленая, другая - красная, как это было вначале.
На бесконечном белом листе клетчатой бумаги конечное число клеток окрашено в черный цвет так, что у каждой черной клетки четное число (0, 2 или 4) белых клеток, соседних с ней по стороне. Докажите, что каждую белую клетку можно покрасить в красный или зеленый цвет так, чтобы у каждой черной клетки стало поровну красных и зеленых клеток, соседних с ней по стороне.
Решение:
Идея решения состоит в следующем. Если соединить центры соседних черных клеток отрезками, то объединение проведенных отрезков разбивает плоскость на области. Из четности степеней вершин следует, что области можно покрасить в два цвета (желтый и синий) так, чтобы области, граничащие по отрезку, имели разные цвета. Далее, покрасим зеленым в синих областях клетки с четной абсциссой, а в желтых - с нечетной. Остальные клетки покрасим красным.
Проведем формальные рассуждения. Введем координаты так, чтобы центры клеток были целочисленными, и будем считать, что окрашены не клетки, а их центры. Вначале окрасим все белые точки «в полоску», т. е. так, чтобы зеленые точки имели четную абсциссу, а красные - нечетную. Пусть граф $Г$ имеет в качестве вершин множество $V$ всех черных точек, а в качестве ребер - множество всех отрезков $E$, соединяющих соседние черные точки. Заметим, что степень каждой вершины в $Г$ четна.
Начнем движение по ребрам из какой-то вершины. Войдя в вершину по некоторому ребру, мы сможем выйти по другому ребру, поэтому когда- нибудь придем в вершину, в которой уже были. Тем самым, в графе найден простой цикл $C$. Ребра $C$ ограничивают на плоскости многоугольник. Изменим цвет у всех красных и зеленых точек, лежащих внутри цикла $C$. Далее, перейдем к рассмотрению графа $Г^{\prime}$, получаемого из $Г$ удалением всех ребер цикла $C$. В графе $Г^{\prime}$ степень каждой вершины четна, поэтому снова найдем простой цикл, произведем перекрашивание, удалим ребра цикла, и т. д. Действуем так до тех пор, пока в соответствующем графе есть ребра.
Докажем, что полученная в конце этого процесса раскраска удовлетворяет условию.
Если у черной точки $P$ четыре белых соседа, то при каждом перекрашивании они находились либо все внутри многоугольника, либо все - вне, а значит перекрашивались одинаковое число раз. Тогда у $P$ по два красных и зеленых соседа, поскольку так было в начальной раскраске.
Пусть у черной точки $P$ два белых соседа $K$ и $L$, и два черных соседа $M$ и $N$.
Пусть $K$ и $L$ лежат в одной горизонтали или в одной вертикали. Тогда $K$ и $L$ находились в разных частях плоскости относительно цикла только при перекрашивании точек внутри цикла, содержащего путь $MPN$. Таким образом, количество перекрашиваний точек $K$ и $L$ отличается на 1. Так как в начальной раскраске $K$ и $L$ одноцветны, то в конечной - разноцветны.
Если же $K$ и $L$ - соседи по диагонали, то при каждом перекрашивании они находились либо обе внутри многоугольника, либо обе - вне, и значит одна из них зеленая, другая - красная, как это было вначале.
