Torens van Hanoi

Inleiding

In dit verslag is het de bedoeling dat we het probleem van de Torens van Hanoi oplossen.
Het probleem luidt:
In Hanoi had volgens de legende een groep priesters de taak een toren van 64 schijven te verplaatsen. De schijven staan op een soort paaltje. Ze mogen daarvoor 3 van die palen gebruiken. Ze mogen maar 1 schijf per keer verplaatsen, en ze mogen ook niet een grote schijf op een kleine schijf plaatsen.
Er werd voorspeld dat wanneer de priesters klaar zouden zijn met deze taak, dat de zon dan is opgebrand, dus dat de wereld dan vergaat.

We gaan er vanuit dat ze 1 schijf per seconde verplaatsen

De hoofdvraag uit dit onderzoek is dus:
Hoe lang duurt het voordat de toren met 64 schijven is verplaatst?

Onderzoek

Om er achter te komen hoe lang het zou duren voordat de toren verplaatst zou zijn hadden wij een klein model gebruikt van de Torens van Hanoi, met 7 schijven.

Waarschijnlijk zou er een verband zitten tussen het aantal schijven dat verplaatst moet worden en het aantal stappen dat daar voor nodig is. We zijn dus begonnen met 1 schijf te verplaatsen, daarna 2, daarna 3, enz.
We kwamen op het volgende:
1 schijf = 1 stap
2 schijven = 3 stappen
3 schijven = 7 stappen
4 schijven = 15 stappen
Verder zijn we niet gegaan want dat vonden we teveel stappen en we dachten dat we met 4 getallen wel een verband zouden vinden en dat is ook gelukt.
Het verband luidt als volgt:
Als er steeds 1 schijf bij komt, wordt het aantal stappen verdubbelt + 1:
1x2+1=3
3x2+1=7
7x2+1=15
we zouden dus een formule kunnen maken: het vorige antwoord x 2 + 1, kort: ans2+1
het zou natuurlijk te lang duren om zo helemaal door te gaan rekenen tot 64 schijven, dus we vullen deze formule in op de grafische rekenmachine. Dat gaat als volgt:

„h menu
„h ga naar recursion
„h voer in: ¡¥2an+1¡¦ (an is te vinden onder F4, hij staat dan bij F2)
„h ga naar range (F5) en voer in: start: 0
end: 64
„h en dan tabel (F6)

Dit betekent: hij begint bij 0 schijven en hij geeft bij elk getal tot aan de 64 het aantal stappen dat ervoor nodig is.

Conclusie

We kunnen nu dus aflezen wat het antwoord is bij 64 schijven.
En toren met 64 schijven heeft ¡¥1.844674407¡P10 tot de macht 19¡¦ stappen nodig om helemaal verplaatst te zijn, dat is dus ook zoveel seconden.
Om iets duidelijker te zijn wat dat getal precies is rekenen we het even om naar jaren:

3600 sec. in een uur, 3600 x 24 = 86400
86400 sec. per dag, 86400 x 365 = 31536000
31536000 sec. per jaar!

1.844674407¡P10^19 : 3153600= 5,849424172¡P10^11 jaar!


Zo veel jaar gaat dat dus duren.