Zitat:
Lösung:
Für dieses Problem gibt's keine Lösung.
Wie kann man das zeigen? Fang mit zwei Häusern (1, 2) und zwei Versorgern (A, B) an. Die Versorgungsleitungen ergeben dann immer ein Viereck, etwa so:
1
/ \
/ \
A B
\ /
\ /
2
Man kann die Linien zwar beliebig verschnörkeln und die Punkte verschieben, aber letztlich ist das Ergebnis immer das gleiche: eine abgeschlossene Fläche innerhalb der vier Leitungen.
So, jetzt kommt der dritte Versorger (C) dazu. Dessen Startpunkt kann innerhalb oder außerhalb der geschlossenen Fläche liegen, und wieder können die Leitungen beliebig verschnörkelt gelegt werden. Wenn man die Leitungen "strafft" und die Punkte etwas zurechtrückt, wird das Ergebnis aber immer so oder ähnlich aussehen:
1 1
/|\ /|\
/ | \ / | \
A C B oder A B C
\ | / \ | /
\|/ \|/
2 2
Damit wird auch schon klar: egal, wo das dritte Haus steht, es kann nicht mehr wie gefrodert mit A, B und C verbunden werden. Wenn es außerhalb liegt, kann es nicht mit dem mittleren der drei Versorger verbunden werden, weil der "eingesperrt" ist. Wenn das dritte Haus in einer der beiden Teilflächen liegt, ist der dritte Versorger "ausgesperrt".
Warum gibt es nun keine Lösung dafür?
Das ist in dieser Ebene nicht möglich. Das läßt sich mit dem Polyeder-Satz von Euler beweisen: dieser Graph, um einen solchen handelt es sich hier, ist nicht planar (ich will das hier nicht näher definieren, das würde den Rahmen sprengen). Es kann hier also keine Lösung geben!
Übrigens: Auf einem Torus ("Reifenschlauch") würde es funktionieren
Danke an Ralf, auf dessen Posting diese FAQ basiert!
Ein weiterer Dank an Björn, der uns folgende ausführlichere Lösung gemailt hat:
Wir sind uns alle einig, dass dieses Rätsel weder auf einem klassischen
zwei- noch auf einem dreidimensionalen Objekt gelöst werden kann. Wir
brauchen also ein Objekt, das keine Vorder- und Rückseite hat, sondern vom Prinzip her nur aus einer Fläche besteht. Die Lösung: eine Möbiusschleife!
Schau mal unter
http://www.kapege.de/Moebius2.php , dann muss ich es hier jetzt nicht haarklein erklären.
Wenn Du nun in die Mitte des Streifens Deine Häuser und Quellen zeichnest,
Gas Wasser Strom
Haus Haus Haus,
und nun zunächst mal vom Gas nach oben eine Linie führst, landest Du zwangsläufig bei den Häusern. Verbinde auf diese Art und Weise alle Häuser mit dem Gas. Vom Wasser machst Du auch wieder eine Linie nach oben, mit der Du beim rechten Haus landen wirst. Verbinde das linke und mittlere Haus über die kurze Distanz mit dem Wasser. Verbinde nun den Strom mit dem mittleren und rechten Haus über die kurze Distanz und zeichne nun über den halben Umfang der Möbiusschleife eine Linie nach oben. Wenn Du auf der "Höhe" der Häuser angekommen bist, zeichne über die Kante und Du landest beim linken Haus.
Somit hast Du alle Häuser mit den Quellen versorgt und keine Linie überschneidet sich!
[
