Эта классическая [1] популярная головоломка состоит из большого прямоугольника, разделенного на пять «комнат». Задача головоломки - пересечь каждую «стену» диаграммы непрерывной линией только один раз. [2]
Решения [ править ]
Внизу: Решение на торе - пунктирная линия находится на обратной стороне тора (анимация)
Как и в случае с семью мостами Кенигсберга , головоломка может быть представлена в графической форме с каждой комнатой, соответствующей вершине (включая внешнюю область как комнату), и две вершины, соединенные ребром, если комнаты имеют общую стену. Поскольку существует более одной пары вершин с нечетным числом ребер, полученный мультиграф не содержит ни эйлерова пути, ни эйлеровой схемы , а это означает, что эта загадка не может быть решена.
Изменив правила, можно решить связанную загадку. Например, позволяя проходить более чем через одну стену за раз (то есть через угол комнаты) или решая головоломку на торе (бублике) вместо плоской плоскости.
Неофициальное доказательство невозможности [ править ]
Даже без использования теории графов нетрудно показать, что у головоломки пяти комнат нет решения. Во-первых, нужно уточнить правила. Все комнаты и линия решения должны быть нарисованы на одной стороне обычного плоского листа бумаги. Линия раствора должна быть непрерывной, но может резко или плавно изгибаться любым способом и даже пересекать себя (но не у стены, поэтому это часто запрещено). Линия решения должна пересекать каждую «стену» ровно один раз, где «пересечение» означает переход полностью от одной к другой из двух комнат, разделенных «стеной», или из комнаты в область за пределами чертежа. . Это предотвращает одновременное «пересечение» двух стен, проводя линию решения через угол, в котором они встречаются. Это также исключает «пересечение»стену, проведя линию раствора до стены, возможно, вдоль нее, но затем оставив стену на той же стороне. Есть 16 «стен», семь разделяющих комнат и девять отделяющих комнаты от области за пределами чертежа.
Метод доказательства - доказательство от противного . То есть мы действуем так, как будто решение существует, и обнаруживаем некоторые свойства всех решений. Это поставило нас в безвыходную ситуацию, и поэтому мы должны сделать вывод, что были неправы - в конце концов, решения нет. [3]
Представьте, что в каждой «комнате» есть «наблюдатель». Наблюдатель может видеть линию решения, когда она находится в его комнате, но не иначе. Когда линия решения будет проведена, он увидит, что она входит в его комнату через одну стену и выходит через другую. Он также может видеть, что очередь начинается в его комнате и / или заканчивается в его комнате. В области за пределами рисунка нет наблюдателя, поэтому есть пять наблюдателей.
Рассмотрим сначала наблюдателей в нижнем левом и нижнем правом помещениях. Каждая из этих комнат имеет четыре стены. Если линия решения начинается в одной из этих комнат, наблюдатель увидит, что линия выходит через стену. Затем он вернется в комнату через другую стену и снова уйдет через третью. Наконец, он вернется в комнату через четвертую стену и закончится. Если линия решения начинается где-то еще, наблюдатель увидит, как линия решения входит и выходит из его комнаты ровно дважды, проходя через все четыре стены в некотором порядке. С этим нет никаких проблем.
Однако рассмотрим наблюдателей в оставшихся трех комнатах. В каждой из этих комнат по пять стен. Если линия решения начинается в одной из этих комнат, ее наблюдатель увидит, что линия уходит (через одну стену), снова входит и выходит снова (еще две стены), а также входит и выходит во второй раз (последние две стены). Если линия решения начинается где-то еще, наблюдатель увидит, как линия решения входит и выходит (две стены), входит и выходит во второй раз (еще две стены) и, наконец, входит через пятую стену и заканчивается (все пять стен были пересечены. , поэтому линия не может снова выйти из комнаты). Итак, мы видим, что для комнат с пятью стенами линия решения должна либо начинаться внутри комнаты, либо заканчиваться внутри комнаты. Другой возможности нет. В наших рассуждениях мы ничего не сказали о том, какие именно стены пересекает линия решения,порядок, в котором он их пересекает или где проходит линия, когда он находится за пределами определенной комнаты. Следовательно, эти аргументы применимы ко всем решениям, которые подчиняются правилам. Опять же, для комнат с пятью стенами линия решения должна либо начинаться, либо заканчиваться внутри комнаты.
Но у нас есть три комнаты с пятью стенами. Линия решения имеет одно начало и один конец, поэтому она может проходить через все пять стен двух из этих комнат. Однако, исчерпав концы, линия не может пройти через все стены третьей пятистенной комнаты. Следовательно, линия решения не может быть проведена в соответствии с правилами.
Заметки [ править ]
- ^ Гарднер 1959 , стр. 112 Гарднер называет задачу (головоломку) «Пересечь сеть» и называет ее одной из старейших топологических головоломок.
- ^ Согласно Norris 1985 , С.207 «Часто встречается эйлерова графики как головоломок. Рассмотрим знаменитый план этажакоторый состоит из пяти комнатсоединенных между собой ивнешней стороны двери на каждой стене. Головоломкачтобы начать в одной или комнате снаружи, пройдите через каждый дверной проем ровно один раз и вернитесь в исходную точку ".
- ^ Этот аргумент является расширением аргумента, изложенного Джейкобсом (1970 , стр. 489-491).
Ссылки [ править ]
- Гарднер, Мартин (1959), The Scientific American книга математических головоломок и отклонений , Нью-Йорк: Саймон и Шустер
- Джейкобс, Гарольд Р. (1970), Математика / Человеческое стремление , WH Freeman, ISBN 0-7167-0439-0
- Норрис, Флетчер Р. (1985), Дискретные структуры: введение в математику для информатики , Прентис-Холл, ISBN 9780132152600
Внешние ссылки [ править ]
- История и решение головоломки 5-комнатного дома Лаборатории Архимеда
