Задача М307‍‍

Назовём смежными две комнаты, соединённые дверью. Отметим красным цветом все «ходы», из которых может состоять путь. Точнее, соединим красным отрезком центры каждых двух смежных комнат. На плоскости получится сеть красных линий (см. рис. 9). Как легко доказать, она разрезает плоскость на равные ромбы. (Каждый «глухой» отрезок стены лежит в отдельном ромбе.)

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

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

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