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)$ .

Hanois tårn: tre disker skal flyttes fra venstre til høyre pinne

Det er en rekursiv sammenheng mellom $F(n)$ og $F(n-1)$ .

Bestem den rekursive sammenhengen. Bruk denne til å bestemme $F(10)$ .

Hanois tårn med ti disker på venstre pinne

Det finnes også en eksplisitt formel for $F$ .

Undersøk og finn denne formelen.

Fasit

$F(3) = 7$

$F(n) = 2 \cdot F(n-1) + 1$ , $\quad F(10) = 1023$

$F(n) = 2^n - 1$

LøsningsforslagKI-generert

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.

\mathbf{F(3) = \underline{\underline{7}}}

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:

F(n) = F(n-1) + 1 + F(n-1) = \underline{\underline{2 \cdot F(n-1) + 1}}

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$

\mathbf{F(10) = \underline{\underline{1023}}}

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:

F(n) = 2^n - 1

Verifisering: Vi setter inn i rekursjonen og sjekker at formelen stemmer:

2 \cdot F(n-1) + 1 = 2 \cdot (2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1 = F(n) \checkmark

Formelen er altså konsistent med rekursjonen. Kombinert med startverdien $F(1) = 2^1 - 1 = 1$ gir dette:

\mathbf{F(n) = \underline{\underline{2^n - 1}}}

Oppgavedata

Kategori: 3
Vanskegrad: 2
Temaer: rekursiv formel, rekursiv sammenheng, utforskning, mønstre
Kompetansemål: Utforske rekursive sammenhenger ved å bruke programmering og presentere egne framgangsmåter