Archive for the 'Beweismethoden' Category

Von mathegenius inspiriert möchte ich nun, wie dort angekündigt einige Überlegungen zum Turm von Hanoi anstellen und vorführen.
Wer die Legende noch nicht kennt, sollte sich diesen Artikel (von mathegenius) ansehen.
Etwas verallgemeinert werde ich in diesem Artikel Überlegungen für beliebig viele Scheiben anstellen, nicht nur für die ursprünglichen 64.
Eine Frage, die sich stellt ist natürlich die nach der Anzahl der nötigen Schritte.
Diese Frage wollen wir zunächst für einige wenige Scheiben beantworten, und dann verallgemeinern.

Wir benennen die drei Stapelplätze dafür zunächst mit A, B und C. Auf dem Platz A liegen die Scheiben in der Ausgangsposition, Ziel soll es sein, sie auf den Platz B zu verlegen. Die Scheiben seien mit 1 bis n benannt, je kleiner die Ziffer dabei ist, desto kleiner sei auch die Scheibe.

Für eine Scheibe ist die Lösung trivial, trotzdem sei sie hier genannt:
Man verschiebt einfach die Scheibe von A nach B.
Wir benötigen einen Schritt.

Auch zwei Scheiben sollten noch kein Problem darstellen:
A --> C
A --> B
C --> B
Dafür brauchen wir drei Schritte.

An die Aufgabe, einen Turm aus drei Scheiben zu verschieben wollen wir systematischer herangehen.
Wie machen wir das?
Naja, wenn wir es irgendwie schaffen könnten, die untere, größte Scheibe auf den Platz B zu befördern, hätten wir unser Problem reduziert. Nun müssten nur noch die beiden Scheiben von A nach B verschoben werden – die Lösung dafür haben wir schon.
Also gut, wir haben den Plan, die große Scheibe auf Platz B zu bringen. Was müssen wir dazu tun? Klar, der Platz B darf nicht belegt sein. Außerdem muss die große Scheibe zum Bewegen frei sein. Wohin mit den Scheiben 1 und 2?
Hm, Glück gehabt, Platz C ist noch nicht benutzt in unserem Gedankenspiel!
Das einzige, was noch zu erledigen ist, ist nun also, die beiden kleineren Scheiben auf Platz C zu verlegen.
Auch das ist aber nicht schwierig – wie man zwei Scheiben verschiebt wissen wir schließlich.
Aber funktionieren auch alle unsere Schritte, ist zwischendurch vielleicht doch ein Platz belegt, den wir vergessen haben?
Versuchen wir einfach mal, alles zusammen zu puzzeln.

1. Verschiebe die beiden oberen Scheiben nach C.
   Das geht in jedem Fall, wir ignorieren einfach die unterste Scheibe und führen dann unsere Lösung für zwei Scheiben durch – wobei natürlich C statt B zu benutzen ist.
2. Lege die große Scheibe von A nach B.
   Das geht auch, schließlich liegen die anderen beiden Scheiben auf C.
3. Verschiebe die beiden Scheiben von C nach B.
   Auch das funktioniert wieder, mit der Lösung für zwei Scheiben.

Wieviele Verschiebungen benötigen wir nun dafür?
Für den ersten Schritt sind es drei, wie wir zuvor herausgefunden haben.
Der zweite Schritt ist nur eine einzige Verschiebung.
Und der dritte Schritt ist wieder eine Bewegung von zwei Scheiben, benötigt also insgesamt ebenfalls drei einzelne Verschiebungen.
Zusammen macht das also sieben Züge.

Aber mit vier Scheiben wird es vielleicht etwas kniffliger. Schließlich können die vier Scheiben ja auch einen Platz mehr blockieren – oder?
Probieren wir einfach mal das gleiche System aus, wie bei drei Scheiben:

1. Verschiebe die drei oberen Scheiben von A nach C.
   Hm. Das ist lösbar, haben wir ja schon gesehen.
   Wir benötigen sieben Verschiebungen.
2. Verschiebe die vierte Scheibe auf Platz B.
   Auch das ist möglich, die anderen Scheiben liegen ja auf Platz C. Machbar in einer einzigen Bewegung.
3. Zum Abschluss, verschiebe die drei Scheiben, die auf C zwischengelagert waren auch nach B.
   Das kostet wiederum sieben Schritte.

Insgesamt brauchen wir also Züge.

Das sollte erstmal reichen. Jetzt versuchen wir noch, das Prinzip ganz allgemein zu beschreiben.
Dabei wollen wir auch sofort herausfinden, wie viele Züge nötig sind.
Führen wir dafür erstmal eine Benennung ein:
Sei also die Anzahl der Schritte, die benötigt werden, um Scheiben zu verschieben.

Nun stellen wir uns vor, wir haben einen Turm aus Scheiben. Für geben wir die triviale Lösung vor, alle weiteren Fälle wollen wir jetzt induktiv lösen.
Dazu nehmen wir an, dass wir den Wert von kennen. Auch wie wir die Scheiben von einem Platz auf den anderen verschieben setzen wir als bekannt voraus.

Jetzt soll es aber auch losgehen, wir beschreiben unser Verfahren:

1. Wir schieben mit dem bekannten Verfahren für Scheiben die obersten Scheiben von Platz A nach C.
   Dafür benötigen wir genau Schritte.
2. Wir legen die größte, gewissermaßen die “neue”, Scheibe auf Platz B.
   Das kostet eine einzige Verschiebung.
3. Nun bewegen wir den hohen Stapel von C nach B, wofür wiederum Züge nötig sind.

Damit haben wir aus der Lösung für Scheiben eine Lösung für $$n$$ Scheiben erhalten!
Weil wir die (schnellste) Lösung für schon kennen, finden wir also auch eine Zugfolge, um 2 Scheiben zu bewegen.
Daraus entwickeln wir dann den Weg für 3 Scheiben, woraus wiederum derjenige mit 4 Scheiben gefunden wird.
So geht es immer weiter, ad infinitum.
Großartig, wir können nun also den Turm von Hanoi lösen, und das für beliebig viele Scheiben!

Auch die Anzahl können wir bestimmen. Schließlich gilt, wie wir gerade gesehen haben, .
Daraus kann man finden. Dass dieser Wert tatsächlich stimmt, ist noch etwas einfacher zu zeigen, als ihn herzuleiten; nämlich mit unserer Induktion.
Denn:

Also ist diese Formel tatsächlich richtig.

Für die in der Legende genannten 64 Scheiben benötigt man daher Verschiebungen.
Würde für jeden Zug eine Sekunde benötigt, so dauerte das Unterfangen (falls es nicht pausiert würde) etwa 584.942.417.355 Jahre an. Das entspricht den auch von mathegenius genannten 5,8 Milliarden Jahrhunderten [bis zum Ende des Universums ;)].
Unvorstellbar!