Turm von Hanoi
Inhalt dieser Seite
Was ist der Turm von Hanoi? 
Lösung
Der Turm aus n Scheiben
Der Turm von Hanoi mit vier Pfosten
Bau des Turms von Hanoi
Mersenne-Zahlen
Zur Geschichte
Der Turm von Hanoi im Internet
Referenzen
.
Zur Hauptseite    "Mathematische Basteleien"

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 seit 1999 sind:
 

Nr.38
Nr.39
Nr.40
Nr.41
Nr.42
Nr.43
Nr.44
Nr.45
Nr.46
Nr.47
Nr.48
2^06.972.593 - 1
2^13.466.917 - 1
2^20.996.011 - 1
2^24.036.583 - 1
2^25.964.951 - 1
2^30.402.457 - 1
2^32.582.657 - 1
2^37.156.667 - 1 
2^42.643.801 - 1
2^43.112.609 - 1
2^ 57.885.161- 1
2.098.960 Stellen
4.053.946 Stellen
6.320.430 Stellen
7.235.733 Stellen
7.816.230 Stellen
9.152.052 Stellen
9.808.358 Stellen
11.185.272 Stellen 
12.837.064 Stellen 
12.978.189 Stellen 
17.425.170 Stellen
1999
1999
2003
2004
2005
2005
2006
2008
2009
2008
2013

Quelle: http://www.mersenne.org/prime.htm


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
A183111  Magnetic Tower of Hanoi

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