Toren van Hanoi

In India staat de Kashi Vishwanath, een eeuwenoude, hindoeïstische tempel van goud, waar volgens de legende de priesters iedere dag 64 gouden wielen over drie pilaren schoven. Ieder wiel heeft een andere grootte. Toen de priesters eeuwen geleden begonnen met dit vreemde spel waren de wielen van groot naar klein gestapeld om de linker pilaar. De priesters verplaatsten de wielen van pilaar naar pilaar, zonder ooit een groter wiel op een kleiner wiel te plaatsen, hopend dat ze op een dag een stapel van 64 wielen van groot naar klein op de rechter pilaar hadden. Deze puzzel staat bekend als de toren van Hanoi.


4. In de volgende afbeelding zie je een toren van Hanoi met drie wielen. Vind het minst aantal stappen dat je hier nodig hebt om alle wielen van de linker pilaar om de rechter pilaar te krijgen.

 


5. In de volgende afbeelding zie je een toren van hanoi met vier wielen. Vind het minst aantal stappen dat je nu nodig hebt.

 


6. Bepaal het minst aantal stappen dat je nodig hebt om een toren van Hanoi met N wielen op te lossen.

 


7. Stel dat de priesters in het verhaal het voor elkaar krijgen om zonder pauze iedere seconde een wiel te verplaatsen en dat ze de optimale strategie gebruiken om hun toren van 64 wielen op te lossen. Bereken hoe lang de priesters dan over het oplossen van de puzzel doen.