|
Was ist der Turm von Hanoi?
Der Turm von Hanoi ist ein klassisches Knobelspiel.
... ... |
In seiner einfachsten Form besteht der Turm aus drei Kreisscheiben,
die ein Loch haben und auf einen Pfosten gesteckt werden.
Die Form erinnert an Pagoden. Das sind vielstöckige Tempeltürme
im fernen Osten. So ist der Name zu erklären. |
Er heißt auch der Turm des Brahmanen. Er und eine Geschichte dazu
wurden 1883 von Édouard Lucas erfunden.
Zum Turm von Hanoi gehören noch zwei freie
Pfosten.
... ...
|
Der Turm steht zu Beginn auf Platz 1.
Man soll ihn auf Platz 2 neu aufbauen. |
... ...
|
Dabei sind zwei Regeln zu beachten:
(I) Man darf immer nur eine Scheibe umlegen.
(II) Man darf eine größere nicht auf eine kleinere Scheibe
legen.
Der Pfosten auf Platz 3 dient als zusätzliches Zwischenlager.
Lösung top
Notation der sieben Züge: 1-2, 1-3, 2-3, 1-2, 3-1, 3-2 und 1-2.
- Es genügt die Platzwechsel festzuhalten.
Dieses ist auch der kürzeste Lösungsweg. Er besteht aus 7=2³-1=2^3-1
Zügen.
Zur Strategie:
Man beachte die kleine grüne Scheibe: Sie wandert von Platz 1
nach 2, nach 3, zurück nach 1 und nach 2. Die Zahlen 1,2,3 werden
zyklisch durchlaufen. Diese Wanderung hilft bei einer Lösung.
Der Turm aus n Scheiben top
Soll man einen Turm mit vier Scheiben umsetzen,
so führt man diesen Vorgang auf das Drei-Scheiben-Problem zurück.
Man setzt in sieben Schritten den Dreierturm von 1 nach 3, legt die gelbe
Scheibe in die Mitte und baut in wiederum sieben Schritten den Turm von
3 auf die gelbe Scheibe auf Platz 2 auf.
Man benötigt mindestens 2x7+1=15=2^4-1 Schritte:
Man kann schrittweise weitergehen:
Für den 5-Scheiben-Turm braucht man mindestens 2x15+1=31=2^5-1
Schritte,
für den 6-Scheiben-Turm mindestens 2x31+1=63=2^6-1 Schritte.
Verallgemeinerung:
Sind n Scheiben vorgegeben, so braucht man mindestens 2^n-1 Schritte.
Das Problem ist in dieser Aufbereitung beliebt, um den Unterschied zwischen
rekursiver Darstellung [(x(1)=1 und x(n+1)=2x(n)+1] und expliziter Darstellung
[x(n)=2^n-1] einer Folge zu demonstrieren.
Der Turm von Hanoi
mit vier Pfosten top
Wie bei vielen Puzzles sind Abänderungen interessant und werfen
neue Probleme auf.
Oben standen drei Pfosten zur Verfügung. Man kann in mindestens
7 Schritten den Turm auf einem freien Pfosten neu aufbauen.
Steht ein vierter Pfosten zur Verfügung, so kommt man mit 5 Zügen
aus.
Anfangsstellung:
Endstellung:
Die Züge heißen 1-3, 1-4, 1-2, 4-2 und 3-2.
Tabelle für n Scheiben (n=2, 3, 4, 5,...)
|
Anzahl der Züge bei 3 Pfosten
|
03, 07, 15, 31, 63,...
|
Sloane A0002256
|
|
Anzahl der Züge bei 4 Pfosten
|
03, 05, 09, 13, 17,...
|
Sloane A007664
|
Gibt man vier Pfosten statt 3 vor, so verringert sich die Mindestzahl
der Züge.
Bau des Turms von Hanoi top
1.Version:
Wenn man auf das Äußere des Spiels keinen Wert legt und
mehr an dem logischen Problem interessiert ist, genügen einfache Pappquadrate
unterschiedlicher Größe oder nummerierte Karten wie die von
"Elfer raus" zum Spielen.
2.Version:
Man kann den Turm von Hanoi wie in der folgendem Bild herstellen. Die
Version mit vier Pfosten ist etwas Besonderes.
Es ist angebracht mehr Kreisscheiben als im Bild anzufertigen.
3.Version:
Im allgemeinen stehen die Pfosten in einer geraden Linie. Die drei
Pfosten können auch ein gleichseitiges Dreieck bilden. Dann wird deutlich,
dass die größte Scheibe nur einmal gelegt werden kann. Das Spielfeld
hat die Form eines Kleeblatts.
Die Maße sind frei wählbar. Eine genaue Beschreibung findet
man in Buch 2.
Mersenne-Zahlen top
Die Zahlen 2^n-1 heißen Mersenne-Zahlen. Sie waren von Interesse,
da man glaubte, in ihnen eine unendliche Folge von Primzahlen gefunden
zu haben. Diese Frage ist nicht entschieden.
Mersenne-Zahlen sind auch heute noch wichtig, weil man unter ihnen
die größten Primzahlen findet.
Für n=2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127 ergeben sich
Primzahlen.
2^127-1 war bis 1952 die größte mit Ziffern bekannte Primzahl.
Sie hat 39 Stellen und heißt 170141183460469231731687303715884105727.
Den Beweis erbrachte Edouard Lucas.
Danach hat man mit Computerhilfe einige kleinere und vor allem immer
größere Mersennesche Primzahlen gefunden.
Die Ergebnisse bis 2004 sind:
|
Nr.38
|
2^06.972.593 - 1
|
2.098.960 Stellen
|
01.06.1999
|
|
Nr.39
|
2^13.466.917 - 1
|
4.053.946 Stellen
|
01.06 1999
|
|
Nr.40
|
2^20.996.011 - 1
|
6.320.430 Stellen
|
02.12.2003
|
|
Nr.41
|
2^24.036.583 - 1
|
7.235.733 Stellen
|
02.06.2004
|
|
Nr.42
|
2^25.964.951 - 1
|
7.816.230 Stellen
|
18.02.2005
|
|
Nr.43
|
2^30.402.457 - 1
|
9.152052 Stellen
|
26.12.2005
|
|
Nr.44
|
2^32.582.657 - 1
|
9,808,358 Stellen
|
04.09.2006
|
Mehr über die Suche kann man auf den folgenden Webseiten nachlesen.
http://www.mersenne.org/prime.htm
http://www.primzahlen.de
Zur Geschichte
top
Der französische Mathematiker Édouard Lucas (1842-1891)
erfand dieses Spiel und verkaufte es als Spielzeug erstmals im Jahre 1883.
Zu diesem Spielzeug dachte sich Lucas eine Geschichte aus, die man
im Internet nachlesen kann. Hindupriester sollten auf Geheiß ihres
Gottes Brahma 64 Scheiben umlegen. Dazu benötigten sie theoretisch
mindestens 2^64-1 = 1.8*10 ^19 Züge. Wird in jeder Sekunde eine Scheibe
umgelegt, so dauert das 580 000 000 000 Jahre (!).
Der Turm von Hanoi im
Internet top
Deutsch
Birgit Bachmann und Stefan R. Müller (Blinde Kuh, Suchmaschine
für Kinder)
Die Türme von
Hanoi (u.a. Online-Spiel)
Wolfgang Appell (Mathe-Zaubergarten mit Spaß)
Der Turm von
Hanoi
Wikipedia
Türme
von Hanoi
Englisch
Amit Singh
111 Hanoi implementations
David E. Wilkins
The
Tower of Hanoi Problem
Eric W. Weisstein (MathWorld)
Tower of Hanoi
Jaap Scherphuis
Tower of Hanoi
Lawrence Hall of Science
Tower
of Hanoi
Miroslav Kolar
Tower of Hanoi (TH) Puzzle
Neil J. A. Sloane
On-Line
Encyclopedia of Integer Sequences
School of Mathematics and Statistics University of St Andrews, Scotland
Lucas'
biography
Wikipedia
Tower of Hanoi
Referenzen top
(1) Martin Gardner, Mathematical Puzzles & Diversions, New York
1959
(2) Pieter van Delft /Jack Botermans: Denkspiele der Welt, München
1980 (1998 neu aufgelegt)
Feedback: Emailadresse auf meiner Hauptseite
URL meiner
Homepage:
http://www.mathematische-basteleien.de/
©
2002 Jürgen Köller
top |