|
Over de torens van Hanoi zijn twee verhalen te vertellen. Een stoer verhaal
en een waar verhaal:
Het ware verhaal
Het spel werd in 1883 uitgevonden door E.Lucas.
Met 4 schijven heet het ook wel Reve's puzzel.
Het stoere verhaal.
De legende gaat dat in de stad Benares onder keizer Fo Hi een boeddhistische
tempel stond. De grote middenkoepel markeerde het midden van de wereld. In deze
koepels waren continu priesters bezig om gouden schijven die op diamanten punten
stonden te verplaatsen.
God plaatste 64 schijven van groot naar klein op één pin.
Zodra de hele stapel naar een andere pin verplaatst is, zal dat het einde van de
wereld betekenen.
Regels:
|
Er mag maar één schijf tegelijk verplaatst worden.
NOOIT mag een grotere schijf bovenop en kleinere liggen. |
Misschien moet je het eerst een paar keer zelf proberen voor wat kleinere
torens. Click maar wat op de stokken en de schijven en het spel wijst zichzelf:
Het eerste wat ons interesseert is natuurlijk: Wanneer is het einde van de
wereld?
Hoeveel zetten zijn nodig om een toren van 64 schijven te verplaatsen?
Dit probleem heeft een prachtige oplossing met het toverwoord:
Het werkt als volgt in stappen:
| 1. |
Stel dat we een
oplossing hebben om een toren van n schijven te verplaatsen, en
dat dat An zetten kost. |
| 2. |
Dan weet ik hoe je een toren
van n + 1 schijven kunt verplaatsen. Dat gaat in drie stappen: |
|
stap 1: |
Verplaats de bovenste n schijven naar een andere
stok. Dat kost An zetten |
|
stap 2: |
Verplaats de onderste schijf naar de nu lege stok. Dat
kost 1 zet |
|
stap 3: |
Verplaats de toren van n schijven boven op de
grootste schijf. Dat kost weer An zetten |
|
|
|
|
In totaal kost een toren van n
+ 1 dan dus An + 1 = An + 1 +
An = 2•An + 1 zetten |
|
Maar we weten hoeveel een toren van één schijf kost; namelijk 1 zet, Dus
A1 = 1
Dat geeft met bovenstaande formule deze tabel:
| schijven (n) |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
... |
| zetten (An) |
1 |
3 |
7 |
15 |
31 |
63 |
127 |
255 |
... |
Omdat de onderste rij steeds ongeveer verdubbeld wordt zal het wel iets met
machten van 2 te maken hebben.
En jawel, een beetje proberen levert als snel de formule : An = 2n - 1
Dus een toren van 64 schijven kost 264 - 1 =
18446744073709551615 zetten
Als elke zet een seconde duurt dan is het einde van de wereld er pas over
ongeveer 585000000000 jaar.
Dat valt wel mee dus....
Twee- Kleuren - Hanoi
Een aardige variant is de volgende.
Bekijk het onderstaande speelbord:
Nu zijn er twee kleuren schijven: zilveren en gouden.
Nog steeds geldt de regel dat een grotere nooit bovenop een kleinere mag liggen.
Bij even grote schijven maakt het niet uit.
De bedoeling is nu om twee torens van dezelfde kleur (monochrome torens) te
maken, en bovendien moeten daarbij de onderste schijven van plaats verwisselen.
Hoeveel zetten kost dat???
En hoe is dat bij grotere torens??????
|
