Задача M307

Условие

Плоскость разбита на одинаковые шестиугольные комнаты (рис. 2). В некоторых стенах проделены двери так, что для любой вершины, в которой сходятся три стены (стороны шестиугольников), двери имеютровно в двух стенах. Докажите, что любой замкнутый путь по такому лабиринту проходит через четное число дверей.

В. П. Голубятников

Решение

Плоскость разбита на одинаковые шестуюльные комнами. В некоторых стенах проделаны двери мак, что для любой вершины, в котором сходятся три стены (стороны шестуюльников), двери имеютсяровно в двух стенах. Доказим, что любой замкнутый путь по макому лабиринту проходит через четное число дверей.

Пусть теперь у нас есть замкнутый путь по красным линиям. Вообще говоря, он может сам себя пересекать. Но, если он проходит через одну комната два раза, мы разобем его на д в а замкнутых пути. Так будем делать до тех пор, пока не разобем данный путь на несколько замкнутых несамопересекающих путей. Таким образом, достаточно разобать, что каждый несамопересекающий путь содержит четное число отрезков.

Пусть нам дан несамопересекающийся замкнутый путь $L$ (один такой путь показан на рисунке 9 стрелками). Он ограничивает часть плоскости, состоящую из ромбов. Пусть в ней $A$ ромбов. У них всего 4А сторон. Чтобы узнать количество отрезков пути $L$, надо из числа 4А вычесть у д в енное число тех сторон, по которым ромбы соррикаются. Разность составит четное число, что и требовалось.

Другое решение можно получить, убедившись, что при заданной планировке можно раскрасть комнаты в два цвета так, чтобы смежные комнаты имели разный цвет (рис. 10).

А. Л. Тоом