Пятикомнатная головоломка

Пазл с пятью комнатами – это классика. ^[1] популярная головоломка с большим прямоугольником, разделенным на пять «комнат». Цель головоломки — пересечь каждую «стенку» диаграммы непрерывной линией только один раз. ^[2]

Решения

Как и в случае с « Семи мостами Кенигсберга» , головоломка может быть представлена в графической форме, где каждая комната соответствует вершине (включая внешнюю область как комнату) и двум вершинам, соединенным ребром, если комнаты имеют общую стену. Поскольку существует более одной пары вершин с нечетным числом ребер, полученный мультиграф не содержит ни эйлерова пути , ни эйлеровой схемы , а это означает, что эту головоломку невозможно решить.

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

Неофициальное доказательство невозможности

Даже не используя теорию графов, нетрудно показать, что головоломка с пятью комнатами не имеет решения. Во-первых, необходимо уточнить правила. Комнаты и линия решения должны быть нарисованы на одной стороне обычного плоского листа бумаги. Линия раствора должна быть непрерывной, но может резко или плавно изгибаться в любом направлении и даже пересекать себя (но не у стены, поэтому это часто запрещено). Линия решения должна пересекать каждую «стену» ровно один раз, где «пересечь» означает полностью пройти из одной в другую из двух комнат, разделенных «стеной», или из комнаты в область за пределами чертежа. . Это исключает возможность «пересечения» двух стен одновременно путем проведения линии решения через угол, в котором они встречаются. Это также исключает возможность «пересечения» стены путем проведения линии раствора до стены, возможно, вдоль нее, но затем оставляя стену на той же стороне. Всего 16 «стен», семь комнат и девять, отделяющих комнаты от зоны за пределами рисунка.

Метод доказательства – доказательство от противного . То есть мы действуем так, как будто решение существует, и обнаруживаем некоторые свойства всех решений. Это ставит нас в безвыходную ситуацию, и поэтому мы должны прийти к выводу, что мы были неправы — в конце концов, решения нет. ^[3]

Представьте, что в каждой «комнате» есть «наблюдатель». Наблюдатель может видеть линию решения, когда она находится в его комнате, но не иначе. Когда будет нарисована линия решения, он увидит, как она входит в его комнату через одну стену и выходит через другую. Он также может видеть, что линия начинается в его комнате и/или заканчивается в его комнате. За пределами рисунка наблюдателя нет, поэтому наблюдателей пять.

Рассмотрим сначала наблюдателей в нижней левой и нижней правой комнатах. Каждая из этих комнат имеет четыре стены. Если линия решения начинается в одной из этих комнат, ее наблюдатель увидит, как линия уходит через стену. Затем он вернется в комнату через другую стену и снова выйдет через третью. Наконец, он вернется в комнату через четвертую стену и закончится. Если линия решения начинается где-то еще, наблюдатель увидит, как линия решения входит и выходит из его комнаты ровно дважды, проходя через все четыре стены в некотором порядке. Во всем этом нет никаких проблем.

Однако обратите внимание на наблюдателей в остальных трех комнатах. Каждая из этих комнат имеет пять стен. Если линия решения начинается в одной из этих комнат, ее наблюдатель увидит, как линия уходит (через одну стену), снова входит и снова выходит (еще две стены), а также входит и выходит во второй раз (последние две стены). Если линия решения начинается где-то еще, наблюдатель увидит, как линия решения входит и выходит (две стены), входит и выходит второй раз (еще две стены) и, наконец, входит через пятую стену и заканчивается (все пять стен пересечены). , поэтому линия не может снова выйти из комнаты). Итак, мы видим, что для комнат с пятью стенами линия решения должна либо начинаться внутри комнаты, либо заканчиваться внутри комнаты. Другой возможности нет. В наших рассуждениях мы ничего не сказали о том, какие именно стены пересекает линия решения, в каком порядке она их пересекает или куда проходит линия, когда она находится за пределами определенной комнаты. Следовательно, эти аргументы применимы ко всем решениям, подчиняющимся правилам. Опять же, для комнат с пятью стенами линия решения должна либо начинаться, либо заканчиваться внутри комнаты.

Но у нас три комнаты с пятью стенами. Линия решения имеет одно начало и один конец, поэтому она может пройти через все пять стен двух таких комнат. Однако, закончившись концы, леска не может пройти через все стены третьей пятистенки. Следовательно, линия решения не может быть проведена в соответствии с правилами.

Примечания

^ Гарднер 1959 , с. 112 Гарднер называет проблему (головоломку) «Пересечение сети» и называет ее одной из старейших топологических головоломок.
^ Согласно Норрису 1985 , стр. 207 «Эйлеровы графики часто встречаются как головоломки. Рассмотрим знаменитый план этажа, который состоит из пяти комнат, соединенных друг с другом и снаружи дверями на каждой стене. Загадка состоит в том, чтобы начать с одной комнаты или с другой. снаружи, пройдите через каждую дверь ровно один раз и вернитесь в исходную точку».
^ Этот аргумент является расширением аргумента, изложенного Джейкобсом (1970 , стр. 489-491).

Ссылки

Гарднер, Мартин (1959), Книга математических головоломок и развлечений Scientific American , Нью-Йорк: Саймон и Шустер
Джейкобс, Гарольд Р. (1970), Математика / Человеческие усилия , WH Freeman, ISBN 0-7167-0439-0
Норрис, Флетчер Р. (1985), Дискретные структуры: введение в математику для информатики , Прентис-Холл, ISBN 9780132152600

Внешние ссылки

История и решение головоломки «5-комнатный дом» от Лаборатории Архимеда

[1] Гарднер 1959 , с. 112 Гарднер называет проблему (головоломку) «Пересечение сети» и называет ее одной из старейших топологических головоломок.

[2] Согласно Норрису 1985 , стр. 207 «Эйлеровы графики часто встречаются как головоломки. Рассмотрим знаменитый план этажа, который состоит из пяти комнат, соединенных друг с другом и снаружи дверями на каждой стене. Загадка состоит в том, чтобы начать с одной комнаты или с другой. снаружи, пройдите через каждую дверь ровно один раз и вернитесь в исходную точку».

[3] Этот аргумент является расширением аргумента, изложенного Джейкобсом (1970 , стр. 489-491).

[1]

[2]

[3]