telprobleem

Laten we $f(x)$ het aantal mogelijke programma's dat Isaac heeft op een $x-daagse$ reis noemen, en $r(x)$ het aantal mogelijke programma's van $x$ dagen waarbij Isaac op de $x^{ste}$ dag uitrust noemen. $f(x)-r(x)$ is dus het aantal mogelijke programma's van $x$ dagen waarbij Isaac op de $x^{ste}$ dag een sport beoefent.

Allereerst volgt uit het feit dat hij geen twee opeenvolgende dagen surft en waterskiet, dat hij de dag nadat hij heeft gesurft of waterskiet uitrust. Als hij de vorige dag heeft uitgerust, kan hij de volgende dag zowel uitrusten als waterskiën als surfen. Hieruit volgt dat $f(x+1)=3 r(x)+f(x)-r(x)=2 r(x) +f(x)$.

Omdat, wat Isaac ook heeft gedaan de vorige dag, hij de volgende dag per mogelijk programma één keer de mogelijkheid heeft om te rusten, geldt dat $r(x)=f(x-1)$.

Op deze manier leiden we de recursieformule $f(x+1)=2 f(x-1) +f(x)$ af.

We kunnen makkelijk controleren dat $f(1)=3$ en $f(2)=5$.

Hieruit volgt:

$f(3)=11$

$f(4)=21$

$f(5)=43$

$f(6)=85$

$f(7)=171$

$f(8)=341$

$f(9)=683$

Het antwoord is dus $683$ mogelijke programma's.