Gondolkodjunk visszafelé! Hány tablettát vehetünk be az utolsó napon?

Csak érdekességképpen: lényegében ugyanez a feladat, ha azt kérdeznénk hányféleképpen lehet felmenni egy tíz lépcsőfokból álló lépcső tetejére, ha vehetjük egyesével, kettesével, hármasával a lépcsőfokokat, és ezeket tetszőleges kombinációban váltogathatjuk. Nézzük ezt először úgy, hogy csak egyesével vagy kettesével léphetünk.

Azt érdemes felismerni, hogy egy adott lépcsőfokra csak az alatta lévő két lépcsőfok egyikéről léphetünk. Ezért például, ha tudjuk, hogy hányféleképpen juthatunk a nyolcadik és hányféleképpen juthatunk a kilencedik lépcsőfokig, akkor ezt a kettőt összeadva megkapjuk, hogy hányféleképpen juthatunk a tizedik lépcsőfokig. Lényegében tehát felállíthatunk egy ún. rekurzív összefüggést, ami N lépcsőfok esetén a megoldást a kisebb N-hez tartozó megoldásokból származtatja. Jelen esetben a rekurzió a jól ismert Fibonacci-számokat fogja adni, amiknél a sorozat következő tagja az előző két tag összege.

Nézzük ezt meg részletesebben kiírva. Legyen N lépcsőfok esetén a feljutás variációinak száma f(N). N = 1 esetén csak egy lehetőség van, ha lépünk egyet, tehát f(1) = 1. N = 2 esetén két lehetőség van, vagy egyesével lépünk fel, vagy rögtön fellépünk a második lépcsőfokra, tehát f(2) = 2. Ezután viszont minden N > 2 esetén f(N) = f(N-1) + f(N-2). Ez alapján rendre kiszámolhatjuk a sorozat következő tagjait: f(3) = 3, f(4) = 5, f(5) = 8, f(6) = 13, f(7) = 21, f(8) = 34, f(9) = 55, f(10) = 89. A tizedik lépcsőfok tetejére tehát 89-féle módon juthatunk fel, ha maximum kettesével vehetjük a lépcsőfokokat.

Ha hármasával is vehetjük a lépcsőfokokat, akkor a rekurziót általánosítanunk kell úgy, hogy a három előző tag összeadásával kapjuk a következőt, vagyis N > 3 esetén f(N) = f(N-1) + f(N-2) + f(N-3). Természetesen ahhoz, hogy ezt a rekurziót el tudjuk indítani, a sorozat első három tagját meg kell adni. f(1) = 1 és f(2) = 2 továbbra is, f(3) megadásához pedig meg kell számolnunk, hányféleképpen juthatunk a harmadik lépcsőfokra. Ennek négy lehetséges módja van, vagy egyesével, vagy teszünk egy dupla lépést, és utána egy szimplát, vagy egy szimplát és utána egy duplát, vagy egy tripla lépést. Ha viszont f(3) = 4, akkor f(4) = f(3) + f(2) + f(1) = 7, f(5) = 13, f(6) = 24, f(7) = 44, f(8) = 81, f(9) = 149, f(10) = 274.

A gyógyszertesztelés esetében is ugyanez a válasz, ha tíz tablettát kell bevenni, vagyis legalább 274 tesztalanyra van szükség. Persze egy variációval egy teszt nem elegendő, ezért ennek a sokszorosa kell a valóságban ahhoz, hogy megfelelő statisztika álljon rendelkezésre.