Hány 12 hosszúságú bitsorozat készíthető, ha egymás mellet nem lehet kettő 0?

Elsőre csak ilyen bonyolultra tudok gondolni, hogy:

(12 alatt 0) + (12 alatt 1) + (11 alatt 2) + (10 alatt 3) + (9 alatt 4) + (8 alatt 5) + (7 alatt 6)

Vagyis amikor legalább 2 nulla van, akkor az utolsó nullát kivéve mindegyik mögé berakunk egy 1-est.

Hogy érthetőbb legyen: mondjuk 3 nulla esetén azt csináljuk, hogy csinálunk egy 10 jegyű számot a 3 nullával (ez lesz (10 alatt 3) féle szám), majd az első és a második nulla mögé rakunk egy-egy egyest, ezáltal 12 hosszú lesz. Az esetek száma nem változik, marad (10 alatt 3).

Én csak egy vázlatot írnék most le, Bongolo jobban rá szokott érni, így ő kiegészítheti, hogy a megoldás matematikailag is korrekt legyen.

Ha általánosan nézzük a feladatot: hány N hosszúságú bitsorozat készíthető az adott szabállyal, akkor a Fibonacci sorozat elemeit kapjuk.

Példa:

N=1: 2 darab

0, 1

N=2: 3 darab

00 nem lehet

01, 10, 11

N=3: 5 darab

000 NEM

001 NEM

010

011

100 NEM

101

110

111

A 3 hosszú sorozatok úgy is megalkothatók, hogy

- a 2 hosszú sorozatok után teszünk egy 1-est (ezzel nem rontjuk el, biztos jó sorozat lesz az eredmény is)

VAGY

- az 1 hosszú után tehetünk: "10"-át, ezzel szintén jó sorozatot kapunk.

Végiggondolható az is, hogy ezzel az összes létező sorozatot megalkottuk. Általánosan is, az N hosszú sorozatokat az N-1 és N-2 hosszú sorozatokból képezhetjük, így a lehetséges sorozatok száma a két eggyel kisebb hosszúságú sorozatok számának összege.

Teljesen jó a #2 válasz, gratulálok! A megoldás tehát az N+2-edik (most 14-edik) Fibonacci szám.

Annak bizonyítása, hogy így minden sorozat előáll: (teljes indukcióval)

N=1-re és 2-re egyértelmű.

Feltesszük, hogy N-re (és a rövidebbekre) igaz.

N+1-re:

A sorozat vagy 1-re, vagy 0-ra végződik. Ha 1-re végződik, akkor az eggyel rövidebb (N hosszú) sorozat tetszőleges ilyen tulajdonságú sorozat lehet. Mivel azokat mind előállítottuk az indukciós feltevés miatt, az 1-re végződő N+1 hosszúakat is mind előállítjuk.

Ha 0-ra végződik egy N+1 hosszú sorozat, akkor az N hosszú sorozat csak 1-re végződhet, az N-1 hosszú pedig tetszőleges ilyen tulajdonságú lehet. Az N-1 hosszúhoz képest tehát '10' kerül a sorozat végére. Az N-1 hosszúakat mind előállítja a módszer, ezért az N+1 hosszú 0-ra végződőeket is.