Gewinner des Weihnachtspreisrätsels von Westönnen

Die Gewinner unseres Weihnachtspreisrätsels stehen fest!

Nun, durch die vielen Tipps trudelten zahlreiche Lösungen ein, die meisten haben wohl durch eine Suchmaschine eine Lösungsseite gefunden. Es gab aber auch Teilnehmer, die sich die Mühe gemacht haben, selber auf die Lösung zu kommen.

Felix Wegener,
jüngstes Vereinsmitglied,
zieht die Gewinner

Wie Euler dem Nikolaus geholfen hat

In den Sommermonaten hat der Nikolaus saisonbedingt nicht allzu viel zu tun. Daher hat ihm der Herrgott die folgende Denksportaufgabe gestellt: Er soll in einem Strich das oben abgebildete Haus zeichnen, ohne den Bleistift dabei abzusetzen. Wie sehr der Nikolaus sich auch bemüht, die Sache will ihm nicht gelingen. Da denkt er sich: ,,Jetzt muss mir der produktivste Mathematiker aller Zeiten helfen,'' und er besucht Leonhard Euler.
Euler fragt ihn: ,,Ist Dir klar, dass Du an einer unteren Ecke des Hauses mit der Zeichnung anfangen musst?'' Da erkennt der Nikolaus, dass er die Sache immer falsch angepackt hat.
Da er gewohnt ist, durch den Schornstein in die Häuser der Menschen zu gelangen, hat er natürlich beim Zeichnen immer mit dem Dach angefangen. ,,Warum klappt es denn an einer anderen Ecke nicht,'' will er nun aber wissen. Darauf antwortet ihm Euler: ,,Es liegt nahe, die Zeichnung in einer Ecke des Hauses zu beginnen und sie wieder in einer Ecke zu beenden. Von allen Ecken, mit denen die Zeichnung nicht begonnen oder beendet wird, müssen dann aber geradzahlig viele Linien ausgehen.''
Das leuchtet dem Nikolaus ein. Nur von den unteren Ecken gehen ungeradzahlig viele Linien aus. Nun hat er aber auch selbst eine Idee: ,,Dann kann die Zeichnung aber niemals durch einen geschlossenen Bleistiftzug entstehen, d.h. wenn man in einer Ecke mit der Zeichnung beginnt, kann man am Ende dort nicht wieder ankommen, weil sonst ja von allen Ecken geradzahlig viele Linien ausgehen müssten.''
Da lobt ihn Euler und sagt: ,,Das hast Du ja schnell erkannt. Dann wirst Du auch sicher schnell ein Argument finden, warum es in der Stadt Königsberg keinen Rundgang geben kann, bei dem alle Brücken der Pregel genau einmal passiert werden.'' Euler zeigt ihm dazu die folgende Skizze des Brückenverlaufs:

Einige e-mails:

...coole Idee mit dem "Haus vom Nikolaus - Rätsel" !!!
Dank eurer zahlreichen Tipps, bin ich fündig geworden.
Also die Antwort lautet: Es gibt 44 Lösungsmöglichkeiten
(man glaubt wirklich nicht, dass es so viele sind)....

...Hallo!

Na das war doch mal ein klasse Rätsel.

Bei der Arbeit gab es nichts anderes mehr als diese Häuser vom Nikolaus!

Unser Stationsarzt wollte schon ein Computerprogramm entwickeln. Und alle anderen waren am verzweifeln.

Doch jetzt ist es geknackt:...

...Derzeit wohne ich zwar in Werl, fühle mich aber dennoch nach wie vor als
Westönnerin, weshalb ich der Versuchung nicht widerstehen konnte, das Rätsel zum
Anlass zu nehmen, um Euch/Ihnen einmal meine Begeisterung für den Westönner Internet- Auftritt mitzuteilen. Natürlich habe ich auch eifrig getüftelt und
bin über den umständlichen (und sehr unsicheren) Weg, eine Art Stammbaum zu
zeichnen, zu dem Ergebnis von vierundvierzig Lösungsmöglichkeiten gekommen. In
der Hoffnung, dass ich keine weitere Variante übersehen habe, verbleibe ich
mit vielen Grüßen und den besten Wünschen an alle Mitarbeiter der homepage für
den Rest-Advent und die Weihnachtszeit.

...Hallo Freunde,
meine Lösung für euer Spitzen-Rätsel lautet: 44 !!!...

Und Euler hat recht; der Nikolaus findet spielend die richtige Begründung.

PD Dr. Norbert Peyerimhoff, Fakultät für Mathematik an der Ruhr-Universität Bochum

Nun zur Lösung: Es gibt insgesamt 88 verschiedene Arten, das Haus vom Nikolaus zu zeichnen! Wer hätte das gedacht bei einem so kleinen Haus! Die beiden unteren Ecken müssen in der Tat Ausgangs- und Endpunkte sein. 44 Lösungen starten in der rechten, 44 Lösungen (die genauso funktionieren wie die ersten 44, nur seitenvertauscht) in der linken Ecke. Jede zweite der 44 Lösungen ist quasi der gleiche Weg, nur rückwärts gezeichnet, also sind es 22 verschiedene Wege im engeren Sinne. So wie unsere Frage gestellt war- Beginn nur in der unteren linken Ecke- war also die richtige Lösung 44!

Aufschreiben einer Lösung
Zum Aufschreiben einer Lösung empfiehlt sich eine Ziffernfolge. Die Ecken des Hauses werden durchnummeriert. Unten links legt man z.B. die Ecke 1 fest. Dann vergibt man die Zahlen 2, 3 und 4 entgegen dem Uhrzeigersinn für die Ecken des Rechtecks. Die Spitze erhält die Zahl 5. Die oben gezeichneten Häuser haben die Darstellungen 142354312, 145321342, 143213542. Eine Lösung kann also durch eine neunstellige Zahl angegeben werden.

Es gibt 44 Häuser
Ein Computerprogramm prüfte alle neunstelligen Zahlen zwischen 111111111 bis 155555552, ob sie eine Lösung darstellen. Es ergaben sich die folgenden 44 Lösungen.

1,2,3,1,4,3,5,4,2
1,2,3,5,4,3,1,4,2
1,2,4,5,3,1,4,3,2
1,3,2,4,5,3,4,1,2
1,3,4,2,3,5,4,1,2
1,3,5,4,2,1,4,3,2
1,4,2,1,3,5,4,3,2
1,4,3,2,1,3,5,4,2
1,4,5,3,1,2,4,3,2

1,2,3,1,4,5,3,4,2
1,2,4,1,3,4,5,3,2
1,2,4,5,3,4,1,3,2
1,3,4,1,2,3,5,4,2
1,3,4,5,3,2,1,4,2
1,3,5,4,2,3,4,1,2
1,4,2,3,4,5,3,1,2
1,4,3,2,4,5,3,1,2
1,4,5,3,2,1,3,4,2

1,2,3,4,1,3,5,4,2
1,2,4,1,3,5,4,3,2
1,3,2,1,4,3,5,4,2
1,3,4,1,2,4,5,3,2
1,3,4,5,3,2,4,1,2
1,3,5,4,3,2,1,4,2
1,4,2,3,5,4,3,1,2
1,4,3,5,4,2,1,3,2
1,4,5,3,2,4,3,1,2

1,2,3,4,5,3,1,4,2
1,2,4,3,1,4,5,3,2
1,3,2,1,4,5,3,4,2
1,3,4,2,1,4,5,3,2
1,3,5,4,1,2,3,4,2
1,3,5,4,3,2,4,1,2
1,4,3,1,2,3,5,4,2
1,4,3,5,4,2,3,1,2
1,4,5,3,4,2,1,3,2 1,2,3,5,4,1,3,4,2
1,2,4,3,5,4,1,3,2
1,3,2,4,3,5,4,1,2
...
1,3,5,4,1,2,4,3,2
1,4,2,1,3,4,5,3,2
1,4,3,1,2,4,5,3,2
1,4,5,3,1,2,3,4,2
1,4,5,3,4,2,3,1,2

Alle Zahlenfolgen beginnen mit 1 und enden mit 2. Folglich gibt es aus Symmetriegründen auch 44 Häuser, die in 2 beginnen und in 1 enden.

Alle Häuser beginnen unten
In den Punkten 1 und 2 stoßen drei Strecken aufeinander, in 3 und 4 vier Strecken, in 5 zwei Strecken.
Die Punkte 3 und 4 müssen demnach zweimal Durchlaufstation sein, 5 einmal. In 1 und 2 ist eine Durchlaufstation und eine Endstelle. Also müssen in 1 und 2 die Streckenzüge beginnen oder enden.
Beginnt man an der Spitze in 5, so müsste man auch in 5 enden. Das ist nicht möglich wegen der ungeraden Streckenzahl in 1 und 2.

Der Sieger ist gezogen...

Es geht- wie oben bereits geschildert- aus historischen Gründen zuerst um das Königsberger Brückenproblem (Königsberg liegt an der Pregel, war vor 1945 die Hauptstadt Ostpreußens und heißt heute Kalingrad). Leonhard Euler (1707-1783) hat sich mit diesem Problem beschäftigt und dabei den (heute so genannten) Eulerschen Satz aufgestellt.

...

...

Das Problem besteht darin, dass man bei einem Rundweg durch Königsberg alle sieben Brücken genau einmal überschreiten sollte. Ist das möglich?
Die Örtlichkeiten kann zu einem Graphen aus vier Punkten mit verbindenden Wegen vereinfachen.

Euler behauptete, dass ein Rundgang vom Startpunkt und wieder zurück zum Startpunkt wegen der ungeraden Anzahl von Wegen, die von den Punkten ausgeht, nicht möglich ist. Nur wenn von jedem Kreuzungspunkt aus eine gerade Anzahl von Wegen zusammenläuft, ist ein Rundweg, bei dem jeder Weg nur einmal genommen wird, möglich. Das ist der Eulerschen Satz. Ein Rundweg dieser Art heißt heute Eulerkreis. Ist der Weg nicht geschlossen, so spricht man vom Eulerweg.
Das Königsberger Brückenproblem ist sozusagen die Keimzelle eines bedeutenden Zweiges der Mathematik, der Graphentheorie als Teil der Diskreten Mathematik.

...

In der Fachsprache der Graphentheorie besteht das "Haus des Nikolaus" aus fünf Knoten, die durch Kanten verbunden sind. Der Graph ist planar, da die Kanten so gezeichnet werden können, dass sie sich nicht kreuzen (Bild). Er ist nicht vollständig, da nicht alle Knoten durch Kanten verbunden sind. Jeder Knoten hat einen Knotengrad. Das ist die Anzahl der Kanten, die an einem Knoten zusammentreffen. Nach dem Eulerschen Satz ist es nicht möglich ist, einen Rundgang über alle Kanten zu machen, da die unteren Punkte des Hauses den Grad 3 haben. Es gibt keinen Eulerkreis.

Wenn man aber unten in einem Punkt beginnt, kann man alle Kanten einmal begehen und endet im anderen Punkt unten. Ein Eulerweg ist möglich.

Quelle: JKoeller oder hier Alle Lösungen als animierte gifs: www.druki.de