Головоломка "Стена"

[Машуля]

Эту головоломку наш факультет решает уже месяц



Нужно соединить все стороны стен.Пройти через каждую можно только один раз.Когда все стены будут пройдены - задание выполнено.Пример:

[Simply-Art]

Это задание решаемо? Я вижу только одно решение, но не знаю разрешено ли оно правилами, если начинать изнутри то решить можно. Ведь сказано соеденить, но не сказано откуда начать

[Машуля]

Сообщение от Simply-Art

Это задание решаемо? Я вижу только одно решение, но не знаю разрешено ли оно правилами, если начинать изнутри то решить можно. Ведь сказано соеденить, но не сказано откуда начать

начинать можно хоть откуда. задание решаемо

[Alar]

А кто сказал, что она решаема, мне кажется, здесь нет решения.

P.S> отсутвие решения тоже решения, только это нужно доказать.

[alexBlack]

Это же вариант задачи о 7-ми мостах. Решена Эйлером в 1736 году.

Двери представляем ребрами, области куда нужно попасть - вершинами. Получаем граф. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. В нашем случае нечетных вершин 4-ре. Т.е. задача все-таки не решаема.

Откуда у Машули такая уверенность ?


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

[Sota]

Головоломка, предложенная Машулей, напомнила мне ещё одну задачу. Я её так и не решил. Думаю решения нет(хотя такой итог тоже можно назвать решением).
Задача гласит:
Существуют три станции: газовая, подающая воду и электричество, а также есть три дома. Нужно подключить каждый дом к каждой станции, причём линии от станций к дому не должный (!!!) пресекатся.
Хотя тут можно физику применить, например: электричество пойдёт по трубам с водой...)))

[alexBlack]

2Sota Если интересно, см. теорию графов, определение планарного графа. Такой граф называется полным двудольным К(3, 3) и не является планарным, сл-но его нельзя расположить на плоскости без пересечений.

[mutabor]

Эту головоломку наш факультет решает уже месяц

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

[JoanM]

Если учитывать, что линия на вершине угла будет пересекать обе стороны угла, то задача решается так:
[IMG]C:\123.jpg[/IMG]

[Stilet]

[IMG]C:\123.jpg[/IMG]

Ух ты, красиво решена ))) Особенно та японка под сакурой