Hányszor dobjuk fel az érmét?

Ennyiféleképpen lehet k darab írás n dobásból, hogy ne legyen egymás mellett kettő írás:

- félrerakunk k-1 fejet

- az n-(k-1) helyre rakjuk a k írást: (n-k+1 alatt k) lehetséges lerakás

- Az első k-1 lerakott írás mögé teszünk egy-egy fejet, így tuti nem lesz két írás egymás után.

Ha nincs kikötés, akkor (n alatt k) lehetőség van.

Vagyis az egyedülálló írás valószínűsége, ha n dobásból k írás lett:

P1(n,k) = (n-k+1 alatt k) / (n alatt k)

Ezt szorozni kell azzal a valószínűséggel, hogy n dobásból k írás lett:

P(n,k) = (n alatt k) · 1/2^n

P1(n,k)·P(n,k) = (n-k+1 alatt k) / 2^n

Annak a valószínűsége pedig, hogy tetszőleges számú írás esetén egyedülálló írás lesz:

P1(n) = Σ (n-k+1 alatt k) / 2^n

ahol a szumma k=0-tól (n+1)/2 egész részéig megy.

A Wolfram alpha ad erre a szummára zárt alakot külön a páros és páratlan n-ek esetén, de nem tudom, hogy jön ki.

Nem tudom, milyen feladat ez, vagy egyáltalán mi a cél? Én programot írnék rá, ami kiszámolja n keresett értékét ez alapján a szumma alapján.

De megoldható Wolfram-mal is, behelyettesítgetve. Ez jön ki:

Páratlan n-eknél (n=2m+1) n=2·18+1 esetén lesz először kisebb:

[link]

0.000460175

Páros n-eknél (n=2m) n=2·19 esetén lesz először kisebb:

[link]

0.000372289

Vagyis n=2·18 a keresett szám, akkor a valószínűség 0.000568808

[link]

Ha megtudsz valamilyen szebb megoldást, érdekelne...

Legyen F és I betűből álló string a dobások sorozata. A keresett stringekben nincs FF rész-string.

0 hosszú string 1-féle lehet

1 hosszú string 2-féle (I, F)

2 hosszú 3-féle (II, FI, IF)

3 hosszú 5-féle (III, FII, IFI, IIF, FIF)

Ezek eddig éppen az F(2)=1, F(3)=2, F(4)=3, F(5)=5 Fibonacci számok. Az F(1) a mínusz egy hosszú stringre jön ki, rendben is, azt is egyféleképpen lehet kirakni... (kissé erőltetetten)

Szóval a sejtésünk szerint n hosszú stringet F(n+2) féleképpen rakhatunk ki, n+1 hosszút pedig F(n+3) féle módon. Legyen ez az indukciós feltevés.

Lássuk be, hogy n+2 hosszú stringet F(n+4) féleképpen rakhatunk ki, ami az n+4-edik Fibonacci szám.

n+2 hosszú stringet kétféleképpen kaphatunk:

- mindegyik lehetséges n+1 hosszú string mögé (amiből F(n+3) féle van az indukciós feltevés szerint) rakunk egy I betűt.

- mindegyik lehetséges n hosszú string mögé (amiből F(n+2) van az indukciós feltevés szerint) rakunk egy I és egy F betűt.

Más nincs.

Vagyis n+2 hosszú stringből F(n+2)+F(n+3) féle van, ami a Fibonacci sorozat definíciója szerint pont F(n+4).

Tehát bizonyítottuk a feltevést teljes indukcióval.

Az előző válaszom az eredeti feladat direkt levezetése volt.

A binomiális együtthatókkal pedig ezt tehetjük mondjuk:

S(n) = Σ (n-k+1 alatt k)

ahol a szumma k=0-tól (n+1)/2 egész részéig megy. Mehet tovább is, ahogy a kérdező is n+1-ig írta #4-ben, mert (n+1)/2 után csupa 0 lesz.

S(n) = (n+1 alatt 0) + (n alatt 1) + (n-1 alatt 2) + ... a végtelenségig (úgyis nullák)

S(n+1) = (n+2 alatt 0) + (n+1 alatt 1) + (n alatt 2) + ... a végtelenségig (úgyis nullák)

Ha ezeket összeadjuk úgy, hogy az (n+2 alatt 0)=1-et kihagyjuk a párosításból, aztán az egymás alatt lévőket páronként összeadjuk, akkor kihasználhatjuk azt a binomiális összefüggést, hogy

(n alatt k) + (n alatt k+1) = (n+1 alatt k+1)

Vagyis:

- (n+1 alatt 0) + (n+1 alatt 1) = (n+2 alatt 1)

- (n alatt 1) + (n alatt 2) = (n+1 alatt 2)

- stb.

Ez lesz:

S(n) + S(n+1) = 1 + (n+2 alatt 1) + (n+1 alatt 2) + (n alatt 3) + ...

ami éppen S(n+2), hisz az 1 írható (n+3 alatt 0) módon is.

Vagyis az S(n) számok kielégítik a Fibonacci összefüggést. Mivel S(0) = 1 és S(1) = 2, ezért S(n) = F(n+2).