Полезная информация

Понравилась мне одна задачка. Почему понравилась? Потому что решение пришло через удачный рисунок. Все задачи, которые сначала кажутся сложными, а потом понятно решаются при помощи удачного рисунка, мне нравятся. Люблю этот метод решения - "Визуализация", а проще - рисовалка.

Кроме того, один из моих любимых методов решения я метафорически называю "Перешнуровка". Представьте себе, что вы долго идете пешком и устали. Надо сесть на пенек и перешнуровать ботинки, дать ногам отдых. А при решении задачи - надо переформулировать ее, посмотреть на нее с другого ракурса.

Итак...

Минотавр живет и работает в лабиринте. В каждой комнате лабиринта соединяются ровно три коридора. Минотавр начал обходить лабиринт из главной комнаты, руководствуясь следующим правилом: если в предыдущей комнате поворачивал налево, то в этой – направо, и наоборот. Докажите, что когда-нибудь минотавр снова окажется в главной комнате.

Для решения нам необходимо оперировать с регулярным графом, в котором степень вершин равна трем.

1. Практически очевидно, что такой граф должен иметь четное количество вершин. Не будем отвлекаться на доказательство.

2. Наглядная форма такого графа (количество вершин равно 16, но эта конкретность не нарушает общности рассуждений):

3. Эта наглядная форма не позволяет пока "зацепиться" за идею доказательства. Поэтому совершим ряд трансформаций графа, которые будут топологически эквивалентны:

4. Последний рисунок дает нам весьма наглядную зацепку. Траектория "направо - налево - направо - налево - и т.д." представлена прямой центральной линией ABCDEFGO.

5. Пусть главная комната - вершина А. Тогда, если вы вошли в нее, совершив правый поворот по дуге С1, то наша дальнейшая траектория будет ABCDEFGO. И наш очередной, - правый, - поворот мы совершим на дугу С1, замкнув маршрут.

Если по той же дуге С1 вы совершаете левый поворот и входите в комнату А с требованием далее совершить правый поворот, то ваша траектория будет более извилистой - ANMBCLKDEJIFGHPO. И ваш очередной, - теперь уже левый, - поворот вы совершите на дугу С1, также замкнув маршрут.

6. "Перешнуруем" задачу. Попробуем, имея центральную магистраль в виде дерева с попеременными правыми и левыми отворотами, намеренно построить траекторию, которая начнется в главной комнате А и потом уйдет в какой-нибудь цикл, минующий эту начальную точку маршрута. 

На рисунке изображен маршрут, который начинается в начальной левой вершине с правым поворотом в бэкграунде (здесь, красные крестики - запретные ответвления) и заканчивается правым поворотом, но мы направляем маршрут не в начальную точку, а в какое-нибудь ответвление. Каждый такой "фокус" приводит к тому, что наш маршрут перекидывается на противоположную сторону от прямой центральной ветки, причем, это происходит при любых вариантах конфигураций центральной магистрали - заканчивается ли она левым или правым поворотом, четное или нечетное количество вершин на этой центральной ветке маршрута, завернем ли мы нашу петлю к верхним или нижним отросткам от магистрали.

Будем далее рассуждать в предположении, что граф представлен конечным множеством вершин. Если мы будем оставлять какую-либо "нить Ариадны" в пройденном маршруте и отсекать таким способом проверенные петли, то конечность графа вынудит нас когда-нибудь зайти снова в главную комнату, завершив маршрут в начальной точке.

Попытка сконструировать цикл маршрута, который будет проходить мимо начальной точки, - не удалась. Считаем утверждение доказанным.