Tower of Hanoi

In een oude stad in Indië, zo vertelt de legende, leefden monniken die zichzelf de opdracht gegeven hadden om 64 schijven van de ene staaf naar de andere over te brengen. De schijven verschillen allen in diameter. Een schijf mag nooit op een smallere schijf geplaatst worden. Drie staven staan ter beschikking.
De monniken begonnen aan hun opdracht, niet wetende hoe lang ze er mee zouden bezig zijn. De legende vertelt verder dat op het moment dat een monnik de laatste schijf bovenop de nieuwe toren plaatst, hun tempel tot stof zal vergaan en het einde van de wereld realiteit wordt. Schuilt er enige waarheid in deze legende?
Ja en neen. Het was een Frans wiskundige die in 1883 deze puzzel ontwikkelde. Een zoektocht op het internet leverde me honderden websites op die deze intrigerende puzzel behandelen. De helft promoot deze puzzel als een opdracht programmeren en de andere helft bespreekt de wiskundige achtergrond.
Het spel zoals ik hier heb, bestaat uit een houten plank met drie stokken. Op één stok staan 8 houten schijven. Je kan nu beslissen om b.v. met drie schijven de puzzel op te lossen. Maar je kan evengoed 4, 5, 6, 7 of 8 schijven gebruiken. In dat laatste geval moet je wel iets meer tijd voorzien. Het minimum aantal stappen dat je nodig hebt, kan berekend worden met een eenvoudige formule: (2 tot de macht n)-1 waarbij n het aantal gebruikte schijven is.
Dus met drie schijven heb je minimum 7 bewegingen nodig, met 4 schijven 15, met 5 schijven 31,... en met 8 schijven 255!
Als je nu terugkeert naar de legende die het over 64 schijven heeft, geeft deze formule het ronde getal van 1,8 x 10 tot de macht 19. Dus dat verhaaltje over het einde van de wereld zal wel kloppen!