Om Tårnet i Hanoi | Regler, 2ⁿ−1 og legenden

Tre pinde og en kegle af skiver

Brættet har tre pinde. Skiverne har alle forskellig størrelse og glider ned over pindene. I starten sidder hele sættet på én pind, sorteret efter størrelse, den største nederst og den mindste øverst, så stakken er en kegle. Målet er at flytte hele tårnet over på en anden pind.

Træ-Tower of Hanoi-puslespil med stablede skiver på tre pinde — Træ-Tower of Hanoi-puslespil. Foto: PranavAmbhore, CC BY-SA 3.0

De tre regler

1. Flyt kun én skive ad gangen. 2. Et træk tager den øverste skive fra en stak og lægger den på en anden stak eller på en tom pind. 3. En større skive må aldrig ligge på en mindre. De tre regler er hele spillet. Med dem er hver lovlig stilling en måde at fordele skiverne på pindene, hvor hver pind forbliver sorteret.

Den korteste løsning er 2ⁿ − 1

Det mindste antal træk, der løser et tårn af n skiver, er 2ⁿ − 1. Én skive tager 1 træk. To skiver tager 3. Tre tager 7, fire 15 og fem 31. Hver ny skive fordobler den forrige løsning og lægger det ene træk til, der flytter den største skive: Hvis n − 1 skiver tager T træk, tager n skiver 2T + 1. Den rekursion er præcis 2ⁿ − 1. Otte skiver, det største tårn i PictorX-appen, tager 255 træk. Der findes ingen kortere lovlig vej.

Sådan virker rekursionen

For at flytte n skiver fra startpinden til målpinden med den tilbageværende pind som hjælpepind: 1. Flyt de øverste n − 1 skiver fra startpinden til hjælpepinden. 2. Flyt den største skive fra startpinden direkte til målpinden. 3. Flyt de n − 1 skiver fra hjælpepinden over på målpinden, oven på den største skive. Trin 2 er lovligt, fordi den største skive må ligge på en hvilken som helst pind. Trin 1 og 3 er det samme puslespil, én skive mindre. Kaldet ender ved en enkelt skive, der flyttes én gang. Foldet ud giver det de 2ⁿ − 1 træk, og intet trin lægger nogensinde en større skive på en mindre.

Kæmpe udendørs Tower of Hanoi ved Domaine de Chanteloup — Kæmpe Tower of Hanoi ved Domaine de Chanteloup. Foto: Als33120, CC BY-SA 4.0

Legenden om de 64 gyldne skiver

Den franske matematiker Édouard Lucas præsenterede puslespillet i 1883. Med det fortalte han en legende om et indisk tempel i Kashi Vishwanath, hvor præster flytter en stak af 64 gyldne skiver efter præcis de samme regler. Når det sidste træk er gjort, siger legenden, går verden under. Fireogtres skiver tager 2⁶⁴ − 1 træk: 18.446.744.073.709.551.615. Med ét fejlfrit træk i sekundet, dag og nat, er det omkring 585 milliarder år. Præsterne bliver ikke færdige.

Portræt af matematikeren Édouard Lucas — Édouard Lucas (1842-1891), der introducerede puslespillet i 1883. Offentlig ejendom

Spil det i PictorX

Åbn Tårnet i Hanoi, og der står allerede et tårn af fire skiver på startpinden. Femten træk er minimum. Træk den øverste skive til en anden pind, eller klik på en pind og derefter på den, du vil have. Tasterne 1, 2 og 3 gør det samme. En større skive på en mindre bliver afvist. Skiver går fra 1 til 8, så du kan holde 1, 3, 7, 15, 31, 63, 127 og 255 op mod formlen. Trin afspiller ét træk af en korteste løsning. Løs afspiller resten. »Se 3 skiver« viser den rekursive strategi i bevægelse. Fortryd og Gentag går gennem dine træk. Gem en PNG, eller åbn brættet i PictorX-editoren.

Ofte stillede spørgsmål

Hvad er reglerne for Tårnet i Hanoi?

Flyt én skive ad gangen. Tag den øverste skive fra en pind, og læg den på en anden pind. Læg aldrig en større skive på en mindre. Hele tårnet starter på én pind og skal ende på en anden.

Hvor mange træk tager den korteste løsning?

2ⁿ − 1. Én skive er 1 træk, to skiver 3, tre 7, fire 15 og fem 31. Hver ekstra skive fordobler den forrige løsning og lægger ét træk til.

Hvem opfandt Tårnet i Hanoi?

Den franske matematiker Édouard Lucas præsenterede det i 1883. Historien om præsterne og de 64 gyldne skiver i Kashi Vishwanath er den legende, han knyttede til puslespillet.

Hvor lang tid ville 64 skiver tage?

2⁶⁴ − 1 træk, altså 18.446.744.073.709.551.615. Med ét træk i sekundet er det omkring 585 milliarder år.