Türme von Hanoi - Wie berechnet man die kleinste Anzahl an Zügen?

Question

Es sind 3 Pfähle und n Scheiben gegeben. Jeder Pfahl kann eine beliebige Anzahl von Scheiben aufnehmen. Dabei müssen die Scheiben nach oben hin jeweils immer kleiner werden. Am Anfang seien alle n Scheiben auf dem ersten Pfahl aufgeschichtet. Geben Sie (mit Begründung) eine Strategie an, um alle Scheiben in weniger als 2^n Schritten vom ersten zum dritten Pfahl zu bringen.

Ich bin mir nicht sicher, ob ich die obige Aufgabenstellung richtig verstanden haben. Ich würde jetzt per Induktionsbeweis vorgehen, von wegen (2^n-1). Aber das wäre ja das klassische Türme Schema, und es soll ja weniger als 2^n Schritte sein

Comments

Vor der gleichen Frage sitze ich auch und bin unschlüssig, welche Antwort erwartet wird.

 

A) Es gibt keine Strategie, welche es ermöglicht das Problem in weniger als 2^n-1 Schritten zu lösen.

oder

B) Angabe einer Strategie, wie z.B. 4 anstelle der 3 Stäbe.

 

Ich tendiere ja zu A), weil die Vorausetzung 3 Stäbe mit n Scheiben ist und den üblichen Regeln zum verschieben der Scheiben.

---

In der Aufgabenstellung steht doch

...  um alle Scheiben in weniger als 2^n Schritten vom ersten zum dritten Pfahl zu bringen.

Es ist also nur gefordert weniger als 2^n Schritte zu benutzen und nicht weniger als 2^n - 1 Schritte.

Wie ich gezeigt habe, gibt es ein Verfahren, was genau 2^n - 1 Schritt benötigt. Das sind ja aber weniger als die geforderten 2^n Schritte. 

Answer 1

1 Scheibe kann ich verschieben in 1 Zug.

2 Scheiben kann ich verschieben indem den oberen Turm aus 1 Scheibe auf den Ausweichstab verschiebe, dann die untere Scheibe verschiebe und dann den Turm vom Ausweichstab verschiebe. 2 * 1 + 1 = 3

3 Scheiben kann ich verschieben indem den oberen Turm aus 2 Scheiben auf den Ausweichstab verschiebe, dann die untere Scheibe verschiebe und dann den Turm vom Ausweichstab verschiebe. 2 * 3 + 1 = 7

4 Scheiben kann ich verschieben indem den oberen Turm aus 3 Scheiben auf den Ausweichstab verschiebe, dann die untere Scheibe verschiebe und dann den Turm vom Ausweichstab verschiebe. 2 * 7 + 1 = 15

Brauch ich also für eine Anzahl von n Scheiben 2^n - 1 Schritte benötige ich für n+1 genau

2*(2n - 1) + 1 = 2*2n - 1 = 2^{n+1} - 1 Schritte

Ich brauche also für n scheiben immer 2^n - 1 Schritte.