Piros és kék gyöngyökből láncot fűzünk. Hányféleképpen készíthetünk n hosszú láncot, ha nem szeretnénk, hogy kék golyók kerüljenek egymás mellé?

Érdekes a felvetés, de nem igazán pontos a feladat.

Ha piros és kék gyöngyök vannak, és n hosszú lehet, és csak annyi a kikötés, hogy kék golyó nem kerülhet egymás mellé, a megoldás kb. végtelen.

Lehet egy full piros.

Lehet egy piros 1 kék 1 piros

Lehet egy piros 1 kék 2 piros

stb.

Lehet egy kék egy piros

lehet egy kék 2 piros egy kék

lehet egy kék 3 piros egy kék

stb.

Ez így kb. végtelenig mehet.

Az előző válaszadó vajon mi alapján gondolta, hogy n darab, azaz véges sok gyöngyöt végtelen különböző módon tud sorba rakni? Érdekes...

A feladat egyébként nagyon szép, és a Fibonacci-sorozatra vezethető vissza.

Talán érdemes szétválasztani az n=páros és n=páratlan eseteket.

Az egyes aleseteket úgy számíthatjuk ki, hogy minden piros gyöngy közötti (illetve az elő piros előtti meg az utolsó utáni) térrészt egy doboznak képzelünk, amelybe csak egyetlen kék gyöngyöt tehetünk.

Ha n páros, azaz n=2k, akkor 0 darab kék gyöngyöt tudunk 2k+1 helyre, vagy 1 db kék gyöngyöt 2k helyre, vagy 2 db kéket 2k-1 helyre, ... vagy i db kéket 2k+1-i helyre tenni, ahol az egyes aleseteknél a sorrend nem számít, vagyis a lehetőségek számát sima kombinációval kaphatjuk meg:

S(2k) = (2k+1 alatt a 0)+(2k alatt az 1)+(2k-1 alatt a 2)+...+(k+1 alatt a k).

Tovább nincs, mert akkor már kettővel kevesebb piros gyöngyünk lenne, mint kék, és erre már nincs megoldás.

Hasonlóan az n=páratlan esetben, azaz ha n=2k+1:

S(2k+1) = (2k+2 alatt a 0)+(2k+1 alatt az 1)+(2k alatt a 2)+...+(k+2 alatt a k)+(k+1 alatt a k+1).

Ha felírjuk ugyanezt n=2k-1-re is, akkor

S(2k-1) = (2k alatt a 0)+(2k-1 alatt az 1)+(2k-2 alatt a 2)+...+(k alatt a k)

Kis gondolkodás után látszik, hogy S(2k+1)=S(2k-1)+S(2k). Ehhez csak azt kell észrevenni, hogy az S(2k-1) összegzésében a (2k alatt a 0) és az S(2k) összegzésében a (2k alatt az 1) a Pascal-háromszög szabályossága alapján (2k+1 alatt az 1), ami éppen az S(2k+1) összegzésében a második tagot adja. Hasonlóan fel lehet összegezni páronként az ezt követő többi tagot is egészen addig, amíg el nem jutunk az S(2k+1) összegzésében az utolsó előtti tagig, (k+2 alatt a k)-ig. Egyedül az S(2k-1) első tagjának és az S(2k) utolsó tagjának nem jut pár, de ezek mindketten 1-et adnak, nevezetesen az S(2k+1) összegzésének első és utolsó tagját, vagyis (2k+2 alatt a 0)-t és a (k+1 alatt a k+1)-et.

Ezzel beláttuk, hogy S(2k+1)=S(2k-1)+S(2k). A teljesség kedvéért teljesen analóg módon be lehet látni azt is, hogy S(2k+2)=S(2k)+S(2k+1). Így általánosan elmondható, hogy

S(n)=S(n-2)+S(n-1), azaz a lehetőségek száma Fibonacci-sorozatot alkot.

Kis kiegészítés az előzőhöz: mivel n=1-re S(n)=2 (vagy egy piros vagy egy kék gyöngy egymagában), ezért jelen esetben a Fibonacci-sorozat ettől kezdve értendő, azaz

n=1 2 (P vagy K)

n=2 3 (PP vagy PK vagy KP)

n=3 5 (PPP vagy PPK vagy PKP vagy KPP vagy KPK)

n=4 8

n=5 13

stb.