Torens van Hanoi
De Torens van Hanoi zijn een klassieke wiskundige puzzel. Drie pinnen, een stapel schijven van verschillende grootte en twee strenge regels: verplaats één schijf tegelijk, en leg nooit een grotere schijf op een kleinere.
Drie pinnen en een kegel van schijven
Het bord heeft drie pinnen. De schijven zijn allemaal verschillend van grootte en schuiven over de pinnen. Aan het begin zit de hele set op één pin, op grootte gesorteerd, de grootste onderaan en de kleinste bovenaan, zodat de stapel een kegel vormt. Het doel is die hele toren naar een andere pin te verplaatsen.
De drie regels
1. Verplaats maar één schijf tegelijk. 2. Een zet pakt de bovenste schijf van een stapel en legt die op een andere stapel, of op een lege pin. 3. Een grotere schijf mag nooit op een kleinere liggen. Die drie regels zijn het hele spel. Daarmee is elke toegestane stelling een manier om de schijven over de pinnen te verdelen terwijl elke pin gesorteerd blijft.
De kortste oplossing is 2ⁿ − 1
Het kleinste aantal zetten waarmee een toren van n schijven wordt opgelost is 2ⁿ − 1. Eén schijf kost 1 zet. Twee schijven kosten 3. Drie kosten 7, vier 15 en vijf 31. Elke nieuwe schijf verdubbelt de vorige oplossing en voegt de ene zet toe die de grootste schijf verplaatst: als n − 1 schijven T zetten kosten, kosten n schijven 2T + 1. Die recursie is precies 2ⁿ − 1. Acht schijven, de hoogste toren in de PictorX-app, kosten 255 zetten. Een kortere toegestane route bestaat niet.
Hoe de recursie werkt
Om n schijven van de startpin naar de doelpin te verplaatsen, met de overgebleven pin als hulppin: 1. Verplaats de bovenste n − 1 schijven van de startpin naar de hulppin. 2. Verplaats de grootste schijf van de startpin rechtstreeks naar de doelpin. 3. Verplaats de n − 1 schijven van de hulppin naar de doelpin, bovenop de grootste schijf. Stap 2 is toegestaan omdat de grootste schijf op elke pin mag liggen. Stap 1 en 3 zijn dezelfde puzzel, één schijf kleiner. De aanroep eindigt bij één schijf, die één keer wordt verplaatst. Uitgevouwen levert dat de 2ⁿ − 1 zetten op, en geen enkele stap legt ooit een grotere schijf op een kleinere.
De legende van de 64 gouden schijven
De Franse wiskundige Édouard Lucas bracht de puzzel in 1883 uit. Hij vertelde er een legende bij over een Indiase tempel in Kashi Vishwanath, waar priesters volgens precies deze regels een stapel van 64 gouden schijven verplaatsen. Als de laatste zet is gedaan, zegt de legende, vergaat de wereld. Vierenzestig schijven kosten 2⁶⁴ − 1 zetten: 18.446.744.073.709.551.615. Met één foutloze zet per seconde, dag en nacht, is dat ongeveer 585 miljard jaar. De priesters worden niet klaar.
Speel het in PictorX
Open Torens van Hanoi en er staat al een toren van vier schijven op de startpin. Vijftien zetten is het minimum. Sleep de bovenste schijf naar een andere pin, of klik op een pin en dan op de pin die je wilt. De toetsen 1, 2 en 3 doen hetzelfde. Een grotere schijf op een kleinere wordt geweigerd. Schijven loopt van 1 tot 8, zodat je 1, 3, 7, 15, 31, 63, 127 en 255 met de formule kunt vergelijken. Stap speelt één zet van een kortste oplossing af. Oplossen speelt de rest af. ‘Kijk naar 3 schijven’ laat de recursieve strategie in beweging zien. Ongedaan maken en Opnieuw doen lopen door je zetten. Sla een PNG op, of open het bord in de PictorX-editor.
Veelgestelde vragen
Wat zijn de regels van de Torens van Hanoi?
Verplaats één schijf tegelijk. Pak de bovenste schijf van een pin en leg die op een andere pin. Leg nooit een grotere schijf op een kleinere. De hele toren begint op één pin en moet op een andere eindigen.
Hoeveel zetten kost de kortste oplossing?
2ⁿ − 1. Eén schijf is 1 zet, twee schijven 3, drie 7, vier 15 en vijf 31. Elke extra schijf verdubbelt de vorige oplossing en voegt één zet toe.
Wie heeft de Torens van Hanoi bedacht?
De Franse wiskundige Édouard Lucas bracht hem in 1883 uit. Het verhaal van de priesters en de 64 gouden schijven in Kashi Vishwanath is de legende die hij aan de puzzel koppelde.
Hoe lang zouden 64 schijven duren?
2⁶⁴ − 1 zetten, oftewel 18.446.744.073.709.551.615. Met één zet per seconde is dat ongeveer 585 miljard jaar.
Gerelateerde gereedschappen
Torens van Hanoi
Verplaats in je browser een toren van schijven over drie pinnen. Eén schijf tegelijk, nooit een grotere op een kleinere. De kortste oplossing is 2ⁿ − 1 zetten.
Naald van Buffon
Laat in je browser naalden op een gestreepte vloer vallen. Tel de kruisingen en zie hoe het experiment van Buffon uit 1777 π schat.
Naald van Buffon
Het naaldprobleem van Buffon uit 1777: waarom een naald die op evenwijdige lijnen valt π schat, hoe de kans 2l/(πd) voor de korte naald uit het oppervlak onder een sinuskromme volgt en waarom het experiment traag convergeert.
Vermenigvuldigingscirkels
Verbind elk getal op een cirkel met zijn veelvoud. Teken een tafel, een cardioïde of een draadfiguur op papier, met krijt of op hout.
Het vermoeden van Collatz
Verken het Collatz-3n+1-probleem in je browser. Volg hagelsteenreeksen, laat een geometrische Collatz-boom groeien en zoom in op de continue Collatz-fractal.
Langtons Mier
Draai Langtons mier in je browser. Bekijk symmetrie, chaos en de snelweg van 104 stappen, en probeer daarna meerkleurige regels, meerdere mieren, een zeshoekig raster en turmites.
Klaar om het te proberen?
Open PictorX in uw browser - geen installatie, geen creditcard vereist om te starten.
Speel Torens van Hanoi