Torens van Hanoi

De Torens van Hanoi is een bekend wiskundig puzzelspel dat in 1883 werd bedacht door de Franse wiskundige Édouard Lucas. Het spel bestaat uit drie staven en een aantal schijven van verschillende grootte die over deze staven kunnen worden verplaatst. Het doel is om alle schijven van de eerste staaf naar de derde staaf te verplaatsen, met behulp van de tweede staaf als tijdelijke opslag. Hierbij gelden de volgende regels:

• Er mag slechts één schijf tegelijk worden verplaatst.
• Een schijf mag alleen op een andere schijf worden geplaatst als deze kleiner is dan de schijf waar hij op komt.
• Er mogen geen schijven op een lege staaf liggen behalve de kleinste schijf.

Oplossing en wiskundige implicaties

De puzzel is een voorbeeld van een recursief probleem, waarbij de oplossing voor een probleem met n schijven afhankelijk is van de oplossing van het probleem met n-1 schijven. Het minimum aantal zetten om de puzzel met n schijven op te lossen is altijd 2ⁿ - 1. Voor bijvoorbeeld 3 schijven is het minimum aantal zetten 2³ - 1 = 7.

Recursieve strategie

Om de puzzel op te lossen voor een willekeurig aantal schijven, kun je een recursieve strategie toepassen:

1. Verplaats eerst de bovenste n-1 schijven naar de middelste staaf.
2. Verplaats de grootste (onderste) schijf naar de eindstang.
3. Verplaats de n-1 schijven van de middelste staaf naar de eindstang.

Legende

Er is ook een legende verbonden aan het spel. Volgens een oude mythe zouden boeddhistische monniken in een tempel bezig zijn met een versie van de Torens van Hanoi waarbij 64 gouden schijven moeten worden verplaatst volgens dezelfde regels. Als ze deze taak voltooien, zou de wereld eindigen. Omdat de benodigde tijd om de puzzel met 64 schijven op te lossen astronomisch groot is (namelijk 2⁶⁴ - 1 zetten), duurt dit volgens de legende millennia.

Het spel is populair geworden in verschillende vakgebieden, zoals wiskunde, informatica en logica, vanwege de uitdagende structuur en de recursieve aard.