[OT4IM]

Это развод,эта задача невыполнима

[OT4IM]

...или кто решил?

[Ученый]

Уже сутки голову ломаю над задачей(((((((

[vanecki]

У задачи нет решения! В такую хорошо на спор играть

[theRadja]

парадокс)

[velena]

Мой знакомый обосновал невыполнимость этой задачи таким образом:
Пусть к двум домам подведены газ, вода и электричество. Между ними существует однозначное соответствие, тогда изобразим это с помощью следующего графа, где точки D1, D2 - дома, точки B, E, G - соответствующие источники.


Предположим что к точке D3 так же проведены источники (соединена линиями с точками B, E, G). Тогда она должна лежать в одной из трех областей обозначенных на рисунке: 1, 2 или 3 (ограниченных линиями). Но от каждой из этих областей отделена хотя бы одна точка, т.е. чтобы провести линию от этой области к точке, например из области 3 к точке G, нужно пересечь границу области. Мы пришли к противоречию.
Можно еще показать, что подобные разделенные области будут в задаче всегда. Пусть есть два дома и два источника, тогда это можно изобразить таким графом.

Но тогда, если дорисовать т. G, то она будет лежать либо в области 2 или в 3 и линии соединения ее с точками D1, D2 будут всегда разделять область 2 или 3 изолируя какую-то из точек от одной из областей.
Вывод: решение задачи при заданных условиях невозможно.
Доказательство можно провести и в обратном порядке.
В теории графов думаю можно найти строгую теорему, которая дает вполне однозначный ответ на задачу без приведенного мной простенького возможно не строгого доказательства.

[velena]