Ballbinge

[daofeishi]

I en ballbinge har du mange røde baller nummerert 1 til n. Du skal nå plukke ut en gruppe baller fra ballbingen, men på grunn av noen irrasjonelle overtroiske tendenser, vil du ikke la baller med etterfølgende tall ligge i samme gruppe. Dermed kan f.eks. ikke ball 2 og 3 eller ball 6 og 7 legges sammen.

1) På hvor mange ulike måter kan du plukke ut grupper av baller som ikke har etterfølgende tall?

For eksempel, hvis ballbingen har baller nummerert 1 til 5, kan du plukke ut:
- 1 gruppe med null baller
- 5 grupper med en ball
- 6 grupper med to baller, nemlig {1,3} {1,4} {1,5} {2,4} {2,5} {3,5}
- 1 gruppe med tre baller, nemlig {1,3,5}
------------------------------------------------------
13 grupper totalt

Gi svaret som en funksjon av n. (Husk å regne med muligheten for ikke å plukke ut noen som helst.)

2)Hvis du plukker ut k baller tilfeldig, hva er sjansen for at du plukker ut en gruppe som oppfyller kravet?

3)Du plukker ut en gruppe baller, og hvis de oppfyller kravet ditt, legger du dem tilbake i ballbingen, og plukker en ny gruppe av samme størrelse. Hvis du mot formodning tilfeldigvis skulle trekke ut en gruppe med baller som ikke oppfyller kravet, kommer du til å svelge en cyanidpille du har spart for slike situasjoner. Hvis det tar deg 10 sekunder å plukke ut en gruppe baller og undersøke dem, hvor lang er da din forventede resterende levetid?

[Knuta]

1. Dette minner meg meget om fibonaccirekka.

[Karl_Erik]

Prøver meg på den første. Vi legger merke til at hvis a[sub]n[/sub] er antall måter for n baller må a[sub]n[/sub] = a[sub]n-1[/sub] + a[sub]n-2[/sub] fordi man med n baller kan lage alle grupper man kunne lage med n-1 baller og dessuten noen ekstra med den siste ballen. Gruppene man kan legge ball n i er alle gruppene som ikke inneholder ball (n-1), og disse er åpenbart alle gruppene man kunne lage med (n-2) baller, eller a[sub]n-2[/sub]. Ved å legge merke til at a[sub]0[/sub]=1 og at a[sub]1[/sub]=2 ser vi at a[sub]n[/sub] må være det (n+1)-te Fibonaccitallet, og formelen for a[sub]n[/sub] blir da formelen for det (n+1)-te Fibonaccitallet som jeg rett og slett ikke orker å skrive ut her, men den ligger vel på denne siden eller noe.

[daofeishi]

Stemmer! Bare en liten skrivefeil der. Du mener nok det (n+2)'te Fibonaccitallet, og funksjonen kan du gjerne skrive som [tex]f(n) = F_{n+2}[/tex] der [tex]F_n[/tex] er Fibonaccitallene, om du ønsker.