Hanois tårn
Spillet «Hanois tårn» består av tre pinner og en mengde disker med ulik radius som skal tres på pinnene.
Når spillet starter, skal alle diskene være plassert på samme pinne. Ingen av diskene skal ha en større disk liggende oppå seg.
Målet er å flytte alle diskene over på én av de to ledige pinnene. Det er bare lov å flytte én disk av gangen. Diskene som ikke flyttes, må ligge på en pinne. Det er aldri lov å plassere en større disk oppå en mindre disk.
Det minste antallet forflytninger du må gjøre for å flytte \(n\) disker kaller vi \(F(n)\).
- Bestem \(F(3)\).
Det er en rekursiv sammenheng mellom \(F(n)\) og \(F(n-1)\).
- Bestem den rekursive sammenhengen. Bruk denne til å bestemme \(F(10)\).
Det finnes også en eksplisitt formel for \(F\).
- Undersøk og finn denne formelen.
a) \(F(3) = 7\)
b) \(F(n) = 2 \cdot F(n-1) + 1\), \(\quad F(10) = 1023\)
c) \(F(n) = 2^n - 1\)
a
Vi skal flytte 3 disker fra venstre pinne til høyre pinne. Kall pinnene A (venstre), B (midtre) og C (høyre), og diskene 1 (minst), 2 (mellom) og 3 (størst).
Strategien er: flytt de to øverste diskene til midtpinnen, flytt den største til høyre, og flytt de to øverste tilbake.
- Disk 1: A → C
- Disk 2: A → B
- Disk 1: C → B
- Disk 3: A → C
- Disk 1: B → A
- Disk 2: B → C
- Disk 1: A → C
Det er altså \(3 + 1 + 3 = 7\) trekk, og vi kan ikke gjøre det på færre.
b
For å flytte \(n\) disker fra pinne A til pinne C bruker vi denne strategien:
- Flytt de øverste \(n-1\) diskene fra A til B. Det krever \(F(n-1)\) trekk.
- Flytt den største disken fra A til C. Det er \(1\) trekk.
- Flytt de \(n-1\) diskene fra B til C. Det krever igjen \(F(n-1)\) trekk.
Den rekursive sammenhengen er:
med startverdien \(F(1) = 1\).
Vi bygger opp tabellen:
| \(n\) | \(F(n) = 2 \cdot F(n-1) + 1\) |
|---|---|
| 1 | \(1\) |
| 2 | \(2 \cdot 1 + 1 = 3\) |
| 3 | \(2 \cdot 3 + 1 = 7\) |
| 4 | \(2 \cdot 7 + 1 = 15\) |
| 5 | \(2 \cdot 15 + 1 = 31\) |
| 6 | \(2 \cdot 31 + 1 = 63\) |
| 7 | \(2 \cdot 63 + 1 = 127\) |
| 8 | \(2 \cdot 127 + 1 = 255\) |
| 9 | \(2 \cdot 255 + 1 = 511\) |
| 10 | \(2 \cdot 511 + 1 = 1023\) |
c
Fra tabellen i b) ser vi at verdiene er \(1, 3, 7, 15, 31, \ldots\) Vi legger merke til at disse er \(2^1 - 1,\; 2^2 - 1,\; 2^3 - 1,\; 2^4 - 1,\; 2^5 - 1, \ldots\)
Vi gjetter at den eksplisitte formelen er:
Verifisering: Vi setter inn i rekursjonen og sjekker at formelen stemmer:
Formelen er altså konsistent med rekursjonen. Kombinert med startverdien \(F(1) = 2^1 - 1 = 1\) gir dette: