Головоломка

[alex_klepnev]

Три дома(головоломка)

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



Получить код для размещения флеш-головоломки у себя в блоге.

Что ж, раз вы заглянули под кат, сразу признаюсь, что выполнить условия этой головоломки невозможно. И это даже доказывается с помощью теоремы Эйлера.

Воспользуемся методом от противного и предположим, что соединить дома, как это требуется в головоломке, всё-таки возможно. В этом случае всякие две точки, изображающие дома или источники воды, электричества, газа, будут соединены цепочкой линий, этих линий будет девять, и в силу теоремы Эйлера они разделят плоскость на 9–6+2=5 областей.

Каждая из пяти областей ограничена по крайней мере четырьмя линиями, так как по условию задачи данные линии не могут пересекаться. Соответственно, число линий должно быть не меньше 1/2*5*4=10, и, следовательно, наше предположение о том, что задача имеет решение, неверно.

Вот, как-то так. Впрочем, я думаю, что те, кто просидел над головоломкой долго, убедились в её нерешаемости даже без всяких Эйлеров и теорем.
Стащено sviridenkov.com/2010/11/15/tridoma.html#more-13...

@темы: наука

Comments

Там раньше бала какая-то хитрость с правой кнопкой, флеш давал глюк и можно было делать.
Но, да, задача не решаема.

[.Харука.]

А я не заглядывая под кат до-о-олго пыталась все сделать))

[alex_klepnev]

.Харука.
Я сам минут десять сидел, пытался соединить.

Феаринг
Но это в обход правил

alex_klepnev
Угу.

У нас, просто, это было в теории графов (задача, а не глюк флеша). Поэтому я, к тому же, знал.