Springen naar inhoud

Kop of munt


  • Log in om te kunnen reageren

#1

DirkBoogaard

    DirkBoogaard


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 24 november 2010 - 17:03

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

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

Plancker

    Plancker


  • 0 - 25 berichten
  • 9 berichten
  • Gebruiker

Geplaatst op 24 november 2010 - 17:36

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?

#3

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 24 november 2010 - 18:15

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.

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.
In theory, there's no difference between theory and practice. In practice, there is.

#4

DirkBoogaard

    DirkBoogaard


  • 0 - 25 berichten
  • 2 berichten
  • Gebruiker

Geplaatst op 24 november 2010 - 19:19

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?

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..

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.

Precies ja..
Iemand enig idee hoe ik het anders kan oplossen?

#5

Getalletjesmonster

    Getalletjesmonster


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 24 november 2010 - 22:25

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% ;)

#6

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 24 november 2010 - 23:01

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.

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).

M.a.w: 20-5 = 15 * ((15+1)/2) = 120 in 20^2

20^2 of 2^20 ? ;)
In theory, there's no difference between theory and practice. In practice, there is.

#7

Getalletjesmonster

    Getalletjesmonster


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 24 november 2010 - 23:40

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 ? ;)


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.

Dus 2^20 lijkt me dan niet!

Veranderd door Getalletjesmonster, 24 november 2010 - 23:42


#8

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 24 november 2010 - 23:51

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)
LaTeX
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-

#9

Getalletjesmonster

    Getalletjesmonster


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 25 november 2010 - 00:01

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.

Veranderd door Getalletjesmonster, 25 november 2010 - 00:01


#10

Getalletjesmonster

    Getalletjesmonster


  • 0 - 25 berichten
  • 8 berichten
  • Gebruiker

Geplaatst op 25 november 2010 - 00:07

Laat maar, volgens mij had Rogier het al bij het juiste eind.

#11

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 25 november 2010 - 12:26

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:
Verborgen inhoud
Als een fout n-rijtje eindigt op (k-1) keer kop, staat er voor die (k-1) keer kop natuurlijk munt, anders was het een goed rijtje. En alles voor die munt + (k-1) kop op het eind mag verder alles zijn zolang het maar fout is, dus dat zijn alle foute rijtjes van n-k.
)
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 %

Veranderd door Rogier, 25 november 2010 - 12:28

In theory, there's no difference between theory and practice. In practice, there is.

#12

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 25 november 2010 - 14:13

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 %

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.

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-

#13

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 25 november 2010 - 14:25

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:
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]])
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. ;)

Veranderd door EvilBro, 25 november 2010 - 14:26


#14

Rogier

    Rogier


  • >5k berichten
  • 5679 berichten
  • VIP

Geplaatst op 25 november 2010 - 15:24

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.

Die zit hem in die laatste -P(n-k,k) term, die wordt >0 zodra n ;) 2k.

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:

Je hebt hem fout overgenomen, de middelste term is niet 2n-k maar 2n-k:

LaTeX

LaTeX

LaTeX

De redenering achter je formule begrijp ik echter niet helemaal, die is iets te vaag neergeschreven voor mij. ;)

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).

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 LaTeX van 'bijna goede' rijtjes: dat zijn alle elementen R uit Fn die eindigen op mkkkk.

1. Indien LaTeX , dan zijn Rm en Rk (dat is het rijtje R met een m respectievelijk k er achteraan geplakt) allebei goed (dus beide LaTeX ).

2a. Indien LaTeX (dus R eindigt op mkkkk), dan is Rk goed (dus RkLaTeX ).

2b. Indien LaTeX dan ziet R eruit als Xmkkkk voor ťťn of andere LaTeX , en omgekeerd LaTeX geldt Xmkkkk LaTeX . Dus iedere LaTeX kun je ťťn op ťťn associŽren met een LaTeX .

3. Indien LaTeX , en niet LaTeX (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.

#15

317070

    317070


  • >5k berichten
  • 5567 berichten
  • Moderator

Geplaatst op 25 november 2010 - 19:58

5. Dus #Gn+1 = 2 * #Gn + #Bn = 2 * #Gn + #Fn-5 = 2 * #Gn + 2n-5 - #Gn-5

Ah, inderdaad, bedankt. Het is me nu helemaal duidelijk. Een interessante manier om zulke problemen aan te pakken trouwens.

En, nog veel belangrijker, we hebben nadenken kunnen vermijden... daar gaan mijn arme hersentjes alleen maar pijn van doen. ;)

A) zo heb je geen inzicht gekregen in het probleem, alleen maar een oplossing.
B) bewijzen dat je algoritme correct is, is moeilijker dan een oplossing vinden :)

Maar ik heb ook mijn code gedraait (matlab)
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;
Resultaat: 262008 ;) Rogier heeft dus gelijk, en ik heb dus ergens een foutje gemaakt.
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-





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures