Directe formule afleiden van de pagodepuzzel

De pagodepuzzel is de puzzel waarbij je drie houten staven krijgt en op één van die staven zit een piramide van schijven. Je wil de pagode verplaatsen naar een andere staaf, je mag maar een schijf per zet verplaatsen en je mag geen grote schijf op een kleine schijf plaatsen.
Het minimum aantal zetten dat nodig is is voor één schijf 1, voor twee schijven 3, voor drie schijven 7. Als je er een rij van maakt, krijg je:
1,3,7,15,31,63,127...
De recursieve formule voor deze rij is F(n)=2(F(n-1))+1 met als beginwaarde 1. Maar wat is hiervan de directe formule?
Bedankt!

Tabbe
Leerling bovenbouw havo-vwo - zaterdag 31 augustus 2024

Antwoord

Die kun je bijna direct aflezen; elk getal is bijna een macht van 2.
Dat moet ook wel want er wordt telkens vrijwel verdubbeld: F(n)=2\cdot F(n-1)+1.
Het lijkt erop dat je altijd 1 van een macht van 2 aftrekt: 1=2^1-1, 3=2^2-1, 7=2^3-1, \ldots, 127=2^7-1.

Even controleren of F(n)=2^n-1. Dat klopt voor n=1, en als het tot en met n-1 klopt, krijgt je F(n)=2\cdot F(n-1)+1=2\cdot(2^{n-1}-1)+1=2\cdot2^{n-1}-2+1=2^n-1.
Het blijft dus kloppen voor alle natuurlijke getallen n.

Dit heet ook wel het probleem van "De Torens van Hanoi" en het is een paar keer op de wisfaq aan de order geweest.

kphart
zondag 1 september 2024

©2001-2025 WisFaq