Laos en kurkuma koekjes en de Toren van Hanoi
Al ietwat oudere kinderen op bezoek en die wilden wel meehelpen koekjes maken; hun eigen idee om zo toch koekjes te kunnen eten. Het resultaat, op de foto slechts 2 van de stapels koekjes van verschillende hoogtes en met verschillende diameters, deed ons denken aan de Toren van Hanoi; uit een soort van beroepsdeformatie. De kinderen niet onmiddellijk. Maar ze kenden het wel, als kleurrijke kinderpuzzel. Meestal met 7, 8 of 9 schijven en met drie staven. Waarom zijn er eigenlijk zo weinig schijven in het geval van de kinderpuzzel? Waarom niet 64, het aantal velden van een schaakbord, of 100, het aantal velden van een dambord?
Als puzzel is de Toren van Hanoi bedacht door de Franse wiskundige Édouard Lucas. Gepubliceerd in 1883 onder het pseudoniem en deels anagram ‘N. Claus (de Siam)’. In de begeleidende instructies wordt melding gemaakt dat het is ontstaan in Tonkin (nu Hanoi) en van een tempel in India waar Brahmanen de ‘Heilige Toren van Brahma’ verplaatsen en opnieuw opbouwen. Daar lagen bij de start op 1 van 3 diamanten staven 64 gouden schijven, met een gat in het midden. Allen met verschillende diameters, op grootte geordend. De grootste onderop en de kleinste bovenop, zodat een kegelvorm ontstaat. Het doel is om de hele stapel naar 1 van de andere staven te verplaatsen, waarbij de volgende regels gelden:
- Er mag slechts één schijf tegelijk worden verplaatst.
- Elke zet bestaat uit het nemen van de bovenste schijf van een van de stapels en deze op een andere stapel of op een lege staaf plaatsen.
- Er mag geen schijf bovenop een schijf worden geplaatst die kleiner is dan deze.
Regels 1 en 2 zijn logisch, anders is het geen puzzel. Regel 3 maakt het tot een echte puzzel. Je kunt nog additionele spelregels toevoegen, zoals begin op staaf 1 en eindig op staaf 3.
Naar verluidt vergaat de wereld als de Brahmanen de ‘Heilige Toren van Brahma’ helemaal hebben verplaatst. Dan volgt onmiddellijk een interessante vraag: hoe lang zouden ze daarmee bezig zijn, als we aannemen dat ze elke seconde een schijf op de goede manier verplaatsen en geen fouten maken die leiden tot extra verplaatsingen? Een leuk wiskundig probleem, vrij simpel via recursie en inductie op te lossen. Het probleem dat we moeten oplossen is hoe vaak we schijven moeten verplaatsen om een toren op een andere staaf te krijgen?
We gaan het meteen generiek oplossen, voor n schijven, met n een natuurlijk getal groter of gelijk aan 1. Laten we om het aantal woorden te verminderen het minimaal aantal verplaatsingen bij een toren van n schijven, Tn noemen. Hoeveel verplaatsingen kost het dan om een toren van n+1 schijven te verplaatsen, oftewel, wat is Tn+1? Het idee is als volgt. Verplaats eerst de bovenste n schijven zodat een nieuwe toren ontstaat met n schijven. Dat zijn Tn bewegingen. Verplaats dan de grootste schijf naar de vrije staaf en zet daar in Tn stappen de toren van n schijven weer op. We hebben nu weer een toren van n+1 schijven. Doel bereikt in Tn+1=2×Tn+1 verplaatsingen. We weten Tn+1 echter nog niet. We hebben wel een recursieve formule afgeleid. Maar hoeveel bewegingen is T64 dan precies? Dan moeten we eerst T63 uitrekenen, en dan T62, et cetera. Onhandig. Kan het sneller? Jazeker!
Als we 1 schijf meer gebruiken hebben we zeker 2 keer meer verplaatsingen nodig, dat blijkt uit bovenstaande formule. Dat ruikt naar machten van 2. En inderdaad. Een toren van 1 schijf kost 1=21-1 beweging. Een toren van 2 schijven kost 3=22-1 bewegingen. Die observaties leiden tot de volgende hypothese: een toren van n schijven kost 2n-1 bewegingen om de toren te verplaatsen naar een andere staaf. Dat is te bewijzen via inductie. We weten dat de hypothese waar is voor n=1 en n=2. Stel nu het waar is voor n. Is het dan ook waar voor Tn+1? Er geldt Tn+1 = 2×Tn+1 (de recursie) = 2×(2n-1)+1 (de inductiestap) = 2n+1-2+1 =2n+1-1. QED. De hypothese is bewezen en daarmee voor altijd waar.
Dan weten we nu onmiddellijk dat T64=264-1. En dat is een nogal groot getal. 18446744073709551615 om precies te zijn. Grote getallen zijn we eerder tegengekomen, onder andere bij atomen in het universum en bij speelkaarten. Stel dat men elke seconde een schijf van een toren met oorspronkelijk 64 schijven verplaatst. In een jaar zitten 31556926 seconden. Dan duurt het verplaatsen van die toren 584554530873 jaar, oftewel bijna 585 miljard jaar. En daarom is die kleurrijke kinderpuzzel versie meestal maar met maximaal 9 schijven.
We denken dat het heelal nu 13,5 miljard jaar bestaat. We hoeven ons duidelijk nog geen zorgen te maken over ‘Heilige Toren van Brahma’. Dus ja, we hebben tijd zat om koekjes te maken. En omdat de kinderen die op bezoek mee wilden werken en bij uitzondering ook geen probleem hadden met een beetje kruidige smaak, koekjes met laos en kurkuma gemaakt, en ook nog met mosterd.