Kop of munt
-
- Berichten: 2
Kop of munt
Hallo,
Ik vroeg me af, wat de kans is op minstens 5 keer achter elkaar kop, als ik een munt 20 keer op gooi.
Natuurlijk gaan we uit van een ideale munt..
Groeten, Dirk
Ik vroeg me af, wat de kans is op minstens 5 keer achter elkaar kop, als ik een munt 20 keer op gooi.
Natuurlijk gaan we uit van een ideale munt..
Groeten, Dirk
-
- Berichten: 9
Re: Kop of munt
zou het dit kunnen zijn?
Je kan op 16 plaatsen een reeks van 5 starten. De overige 15 mogen gelijk wat zijn. Dit geeft dan 16*2^15 als juiste mogelijkheden. Alle mogelijkheden samen is 2^20. 2^19/2^20 = 1/2?
Je kan op 16 plaatsen een reeks van 5 starten. De overige 15 mogen gelijk wat zijn. Dit geeft dan 16*2^15 als juiste mogelijkheden. Alle mogelijkheden samen is 2^20. 2^19/2^20 = 1/2?
- Berichten: 5.679
Re: Kop of munt
Alleen dan tel je mogelijkheden dubbel, bijvoorbeeld combinaties waarin 6x kop achter elkaar staat tellen 2x mee.Je kan op 16 plaatsen een reeks van 5 starten. De overige 15 mogen gelijk wat zijn. Dit geeft dan 16*2^15 als juiste mogelijkheden.
Ga maar na als je niet 20 maar 6 keer gooit. Er zijn dan 3 (en niet 4) mogelijke combinaties met minstens 5x kop achter elkaar.
In theory, there's no difference between theory and practice. In practice, there is.
-
- Berichten: 2
Re: Kop of munt
Zo iets dacht ik in eerste instantie ook, maar ik vond dat antwoord te toevallig en kwam er dus achter dat dat niet waar kon zijn, omdat je dus combinaties dubbel telt..Plancker schreef:zou het dit kunnen zijn?
Je kan op 16 plaatsen een reeks van 5 starten. De overige 15 mogen gelijk wat zijn. Dit geeft dan 16*2^15 als juiste mogelijkheden. Alle mogelijkheden samen is 2^20. 2^19/2^20 = 1/2?
Precies ja..Rogier schreef:Alleen dan tel je mogelijkheden dubbel, bijvoorbeeld combinaties waarin 6x kop achter elkaar staat tellen 2x mee.
Ga maar na als je niet 20 maar 6 keer gooit. Er zijn dan 3 (en niet 4) mogelijke combinaties met minstens 5x kop achter elkaar.
Iemand enig idee hoe ik het anders kan oplossen?
-
- Berichten: 8
Re: Kop of munt
Als je 5 worpen hebt is het simpel.
Teken eens zes rondjes, stel er 5 of 6 zwart voor, je krijgt dan 3 mogelijkheden.
Teken er 7, 3*5; 2*6 en 1*7.
M.a.w: 20-5 = 15 * ((15+1)/2) = 120 in 20^2
Dus 30%
Teken eens zes rondjes, stel er 5 of 6 zwart voor, je krijgt dan 3 mogelijkheden.
Teken er 7, 3*5; 2*6 en 1*7.
M.a.w: 20-5 = 15 * ((15+1)/2) = 120 in 20^2
Dus 30%
- Berichten: 5.679
Re: Kop of munt
Als ik je goed begrijp zijn er volgens jouw uitleg met 7 worpen (of rondjes), 6 mogelijkheden (3+2+1). Maar dat klopt niet, het zijn er 8 (namelijk 5 met 5: x011111, 0111110, en 111110x waarbij x 0 of 1 mag zijn dus die tellen voor twee! en inderdaad 2 met 6, en 1 met 7, is samen 5+2+1=8).Getalletjesmonster schreef:Als je 5 worpen hebt is het simpel.
Teken eens zes rondjes, stel er 5 of 6 zwart voor, je krijgt dan 3 mogelijkheden.
Teken er 7, 3*5; 2*6 en 1*7.
20^2 of 2^20 ?M.a.w: 20-5 = 15 * ((15+1)/2) = 120 in 20^2
In theory, there's no difference between theory and practice. In practice, there is.
-
- Berichten: 8
Re: Kop of munt
Dan is het dus als er 20 worpen zijn, kun je eigenlijk ook zeggen 15 + 15^2? = 240 uit de 400 permutaties? Lijkt me dan wel, want de overige 15 maken dan geen flikker meer uit wat ze zijn. Dus feitelijk het dubbele van mijn originele antwoord.Rogier schreef:Als ik je goed begrijp zijn er volgens jouw uitleg met 7 worpen (of rondjes), 6 mogelijkheden (3+2+1). Maar dat klopt niet, het zijn er 8 (namelijk 5 met 5: x011111, 0111110, en 111110x waarbij x 0 of 1 mag zijn dus die tellen voor twee! en inderdaad 2 met 6, en 1 met 7, is samen 5+2+1=8).
20^2 of 2^20 ?
Dus 2^20 lijkt me dan niet!
- Berichten: 5.609
Re: Kop of munt
Ten eerste: er zijn 2^20 combinaties.
Ten tweede: er zijn 2^15 combinaties
11111 xxxxx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
01111 1xxxx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
x0111 11xxx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
xx011 111xx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
xxx01 1111x xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
xxxx0 11111 xxxxx xxxxx
Ronde 2:
er zijn 2^14 combinaties
xxxxx 01111 1xxxx xxxxx
Hiervan hebben we er al 1 geteld
er zijn 2^14 combinaties
xxxxx x0111 11xxx xxxxx
Hiervan hebben we er al 1+2=3x1 geteld
er zijn 2^14 combinaties
xxxxx xx011 111xx xxxxx
Hiervan hebben we er al 2+2+4=4x2 geteld
er zijn 2^14 combinaties
xxxxx xxx01 1111x xxxxx
Hiervan hebben we er al 4+4+4+8=5x4 geteld
er zijn 2^14 combinaties
xxxxx xxxx0 11111 xxxxx
Hiervan hebben we er al 8+8+8+8+16=6x8 geteld
Derde en laatste ronde:
er zijn 2^14 combinaties
xxxxx xxxxx 01111 1xxxx
Hiervan hebben we er al 16+16+16+16+16+32=5x16+32=7x16 geteld
er zijn 2^14 combinaties
xxxxx xxxxx x0111 11xxx
Hiervan hebben we er al 6x32+64=8x32 geteld
er zijn 2^14 combinaties
xxxxx xxxxx xx011 111xx
Hiervan hebben we er al 7x64+128=9x64 geteld
er zijn 2^14 combinaties
xxxxx xxxxx xxx01 1111x
Hiervan hebben we er al 8x128+256=10x128 geteld
er zijn 2^14 combinaties
xxxxx xxxxx xxxx0 11111
Hiervan hebben we er al 9x256+512=11x256 geteld
eindresultaat: er zijn 2^15+15x2^14 -1-3x1-4x2-5x4-6x8-7x16-8x32-9x64-10x128-11x256 combinaties.
Dit zijn 273408 combinaties
De kans is dus 273408 op 2^20, dat is 267/1024 of 26,07%
In het algemeen, de kans op een serie van k keer kop in n worpen is: (met n>2k-2)
Ten tweede: er zijn 2^15 combinaties
11111 xxxxx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
01111 1xxxx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
x0111 11xxx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
xx011 111xx xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
xxx01 1111x xxxxx xxxxx
er zijn 2^14 NIEUWE combinaties
xxxx0 11111 xxxxx xxxxx
Ronde 2:
er zijn 2^14 combinaties
xxxxx 01111 1xxxx xxxxx
Hiervan hebben we er al 1 geteld
er zijn 2^14 combinaties
xxxxx x0111 11xxx xxxxx
Hiervan hebben we er al 1+2=3x1 geteld
er zijn 2^14 combinaties
xxxxx xx011 111xx xxxxx
Hiervan hebben we er al 2+2+4=4x2 geteld
er zijn 2^14 combinaties
xxxxx xxx01 1111x xxxxx
Hiervan hebben we er al 4+4+4+8=5x4 geteld
er zijn 2^14 combinaties
xxxxx xxxx0 11111 xxxxx
Hiervan hebben we er al 8+8+8+8+16=6x8 geteld
Derde en laatste ronde:
er zijn 2^14 combinaties
xxxxx xxxxx 01111 1xxxx
Hiervan hebben we er al 16+16+16+16+16+32=5x16+32=7x16 geteld
er zijn 2^14 combinaties
xxxxx xxxxx x0111 11xxx
Hiervan hebben we er al 6x32+64=8x32 geteld
er zijn 2^14 combinaties
xxxxx xxxxx xx011 111xx
Hiervan hebben we er al 7x64+128=9x64 geteld
er zijn 2^14 combinaties
xxxxx xxxxx xxx01 1111x
Hiervan hebben we er al 8x128+256=10x128 geteld
er zijn 2^14 combinaties
xxxxx xxxxx xxxx0 11111
Hiervan hebben we er al 9x256+512=11x256 geteld
eindresultaat: er zijn 2^15+15x2^14 -1-3x1-4x2-5x4-6x8-7x16-8x32-9x64-10x128-11x256 combinaties.
Dit zijn 273408 combinaties
De kans is dus 273408 op 2^20, dat is 267/1024 of 26,07%
In het algemeen, de kans op een serie van k keer kop in n worpen is: (met n>2k-2)
\(\frac{2^{n-k} + 2^{n-k-1}(n-k) -1 - \displaystyle\sum\limits_{i=0}^{n-2k-2} 2^i (i+3)}{2^n}\)
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
-
- Berichten: 8
Re: Kop of munt
Stom, ik heb hem denk ik al: Als je nou eens een raster hebt van 4 stuks, dan heb je 4^2 permutaties * 2 mogelijkheden per permutatie.... = 32.
Als je dus bijv 9 worpen hebt, moeten er altijd 5 op volgorde zijn. Het maakt niet uit hoe die andere dan gerangschikt zijn, klopt? (Ik probeer hier ook wat van op te steken). Het gaat dus om het complementaire gedeelte.
Dus bij 20 heb je dan schijnbaar totaal 20^2 * 2 = 800 permutaties. 15 van hen maakt niet uit, dus dat zijn dan 450 permutaties.
Als je dus bijv 9 worpen hebt, moeten er altijd 5 op volgorde zijn. Het maakt niet uit hoe die andere dan gerangschikt zijn, klopt? (Ik probeer hier ook wat van op te steken). Het gaat dus om het complementaire gedeelte.
Dus bij 20 heb je dan schijnbaar totaal 20^2 * 2 = 800 permutaties. 15 van hen maakt niet uit, dus dat zijn dan 450 permutaties.
- Berichten: 5.679
Re: Kop of munt
Volgens mij gaat er nog iets mis 317070, ik had zelf deze benadering en ik kom op een iets ander antwoord:
Ik noem een kop/munt rijtje "goed" als er minstens k keer achter elkaar kop in voorkomt, en anders "fout".
Definieer nu P(n,k) = het aantal goede rijtjes van n lang.
Alle rijtjes van (n+1) lang tezamen (dat zijn er in totaal 2n+1) zijn natuurlijk alle rijtjes van n met kop er achteraan, en diezelfde rijtjes van n met munt erachteraan.
P(n+1,k) is dan: om te beginnen tweemaal P(n,k), want alle goede rijtjes van n lang, zijn ook goed als er een extra kop of munt achteraan komt. Plus nog eenmaal alle foute rijtjes van n lang die eindigen op (k-1) keer kop, want die worden goed wanneer er een extra kop achteraan komt.
Dat laatste is precies het aantal foute rijtjes van n-k lang, met munt en k-1 keer kop er achteraan. (toelichting:
Dat aantal foute rijtjes van n-k lang is 2n-k min het aantal goede rijtjes van n-k, oftewel 2n-k - P(n-k,k).
Conclusie: P(n+1,k) = 2*P(n,k) + 2n-k - P(n-k,k) (waarbij P(n,k) = 0 als n<k, en P(n,k) = 1 als n=k)
Op die manier kom ik aan P(6,5) = 3, P(7,5) = 8, P(8,5) = 20, enzovoort tot P(20,5) = 262008.
De kans is daarmee 262008/220 24.987 %
Ik noem een kop/munt rijtje "goed" als er minstens k keer achter elkaar kop in voorkomt, en anders "fout".
Definieer nu P(n,k) = het aantal goede rijtjes van n lang.
Alle rijtjes van (n+1) lang tezamen (dat zijn er in totaal 2n+1) zijn natuurlijk alle rijtjes van n met kop er achteraan, en diezelfde rijtjes van n met munt erachteraan.
P(n+1,k) is dan: om te beginnen tweemaal P(n,k), want alle goede rijtjes van n lang, zijn ook goed als er een extra kop of munt achteraan komt. Plus nog eenmaal alle foute rijtjes van n lang die eindigen op (k-1) keer kop, want die worden goed wanneer er een extra kop achteraan komt.
Dat laatste is precies het aantal foute rijtjes van n-k lang, met munt en k-1 keer kop er achteraan. (toelichting:
Verborgen inhoud
)Dat aantal foute rijtjes van n-k lang is 2n-k min het aantal goede rijtjes van n-k, oftewel 2n-k - P(n-k,k).
Conclusie: P(n+1,k) = 2*P(n,k) + 2n-k - P(n-k,k) (waarbij P(n,k) = 0 als n<k, en P(n,k) = 1 als n=k)
Op die manier kom ik aan P(6,5) = 3, P(7,5) = 8, P(8,5) = 20, enzovoort tot P(20,5) = 262008.
De kans is daarmee 262008/220 24.987 %
In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 5.609
Re: Kop of munt
Dat vind ik vreemd, want in mijn redenering verandert de 'structuur' van het antwoord, van zodra n>2k. Bij jou zie ik die structuurverandering niet.Rogier schreef:Op die manier kom ik aan P(6,5) = 3, P(7,5) = 8, P(8,5) = 20, enzovoort tot P(20,5) = 262008.
De kans is daarmee 262008/220 24.987 %
P(n+1,k) = 2*P(n,k) + 2n-k - P(n-k,k)
Dus stel n=3 en k=1 (Wat is de aantal mogelijkheden op 1 kop in 3 gooien?) Die is eenvoudig te tellen en het antwoord is 2^3-1=7
Met jouw formule:
P(3,1) = 2*P(2,1) +5 - P(2,1)
P(3,1) = 2*(2*P(1,1) + 4 - 1) +5 - (2*P(1,1) + 4 - 1)
P(3,1) = 2*(2+4-1)+5-(2+4-1)
P(3,1) = 2*5+5-5
P(3,1) = 10
Met mijn formule:
P(3,1) = 2^2 +2*2 -1 = 7
De redenering achter je formule begrijp ik echter niet helemaal, die is iets te vaag neergeschreven voor mij.
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
-
- Berichten: 7.068
Re: Kop of munt
Je moet ook niet nadenken... dat kan alleen maar tot fouten leiden.
Dus, niet nadenkend, veronderstel ik een formule f(n,a,b,c,d,e) die het aantal mogelijkheden geeft om een reeks te hebben met n posities waarvan de reeks begint met a,b,c,d,e en er nooit 5 enen achter elkaar voorkomen. Haskell erop loslaten:
De functie g(n) geeft het aantal mogelijkheden van reeksen van lengte n met minstens 5 opvolgende enen. g(20) even invullen en je komt op 262008. Het antwoord van Rogier klopt dus. En, nog veel belangrijker, we hebben nadenken kunnen vermijden... daar gaan mijn arme hersentjes alleen maar pijn van doen.
Dus, niet nadenkend, veronderstel ik een formule f(n,a,b,c,d,e) die het aantal mogelijkheden geeft om een reeks te hebben met n posities waarvan de reeks begint met a,b,c,d,e en er nooit 5 enen achter elkaar voorkomen. Haskell erop loslaten:
Code: Selecteer alles
f _ 1 1 1 1 1 = 0
f 5 _ _ _ _ _ = 1
f n a b c d e = (f (n-1) b c d e 0) + (f (n-1) b c d e 1)
g n = (2^n) - (sum [f n a b c d e | a <- [0,1], b <- [0,1], c <- [0,1], d <- [0,1], e <- [0,1]])
- Berichten: 5.679
Re: Kop of munt
Die zit hem in die laatste -P(n-k,k) term, die wordt >0 zodra n 2k.Dat vind ik vreemd, want in mijn redenering verandert de 'structuur' van het antwoord, van zodra n>2k. Bij jou zie ik die structuurverandering niet.
Je hebt hem fout overgenomen, de middelste term is niet 2n-k maar 2n-k:Dus stel n=3 en k=1 (Wat is de aantal mogelijkheden op 1 kop in 3 gooien?) Die is eenvoudig te tellen en het antwoord is 2^3-1=7
Met jouw formule:
\(P_{3,1} = 2P_{2,1} + 2^1 - P_{1,1}\)
\(P_{3,1} = 2 \underbrace{\left(2P_{1,1} + 2^0 -P_{0,1}\right)}_{=P_{2,1} } + 2^1 - P_{1,1}\)
\(P_{3,1} = 2( 2 \cdot 1+1-0 ) + 2 - 1 = 7\)
Misschien als volgt, ik hou het voor de duidelijkheid nu even bij 5 keer kop achter elkaar (de redenering en dus bovenstaande formule geldt uiteraard ook voor andere aantallen).De redenering achter je formule begrijp ik echter niet helemaal, die is iets te vaag neergeschreven voor mij.
Stel Gn en Fn zijn de verzamelingen van alle goede en foute rijtjes van n lang. Dus ieder element R uit Gn of Fn is een rijtje van n keer k(op) of m(unt) achter elkaar. De rijtjes uit Gn bevatten 'kkkkk', die uit Fn niet.
Merk op dat #Fn (het aantal foute rijtjes van lengte n) altijd gelijk is aan 2n - #Gn.
Ik definieer tevens een deelverzameling
\(B_n \subseteq F_n\)
van 'bijna goede' rijtjes: dat zijn alle elementen R uit Fn die eindigen op mkkkk.1. Indien
\(R \in G_n\)
, dan zijn Rm en Rk (dat is het rijtje R met een m respectievelijk k er achteraan geplakt) allebei goed (dus beide \(\in G_{n+1}\)
).2a. Indien
\(R \in B_n\)
(dus R eindigt op mkkkk), dan is Rk goed (dus Rk\(\in G_{n+1}\)
).2b. Indien
\(R \in B_n\)
dan ziet R eruit als Xmkkkk voor één of andere \(X \in F_{n-5}\)
, en omgekeerd \(\forall X \in F_{n-5}\)
geldt Xmkkkk \(\in B_n\)
. Dus iedere \(R \in B_n\)
kun je één op één associëren met een \(X \in F_{n-5}\)
.3. Indien
\(R \in F_n\)
, en niet \(R \in B_n\)
(dus R eindigt niet op mkkkk), dan is noch Rm noch Rk goed.4. Dus ieder rijtje uit Gn+1 kan uitsluitend uit een rijtje van n worden geconstrueerd op manier 1 of 2.
5. Dus #Gn+1 = 2 * #Gn + #Bn = 2 * #Gn + #Fn-5 = 2 * #Gn + 2n-5 - #Gn-5
In theory, there's no difference between theory and practice. In practice, there is.
- Berichten: 5.609
Re: Kop of munt
Ah, inderdaad, bedankt. Het is me nu helemaal duidelijk. Een interessante manier om zulke problemen aan te pakken trouwens.5. Dus #Gn+1 = 2 * #Gn + #Bn = 2 * #Gn + #Fn-5 = 2 * #Gn + 2n-5 - #Gn-5
A) zo heb je geen inzicht gekregen in het probleem, alleen maar een oplossing.En, nog veel belangrijker, we hebben nadenken kunnen vermijden... daar gaan mijn arme hersentjes alleen maar pijn van doen.
B) bewijzen dat je algoritme correct is, is moeilijker dan een oplossing vinden
Maar ik heb ook mijn code gedraait (matlab)
Code: Selecteer alles
count = 0;
for i=1:2^20
b = bitget(uint32(i),1:20);
b = b(1:20) + [b(2:20) 0] + [b(3:20) 0 0] + [b(4:20) 0 0 0] + [b(5:20) 0 0 0 0];
if sum(b==5)
count = count+1
end;
end;
What it all comes down to, is that I haven't got it all figured out just yet
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-
And I've got one hand in my pocket and the other one is giving the peace sign
-Alanis Morisette-