voetbalstickers (deel 2)

Heb je een leuke wiskunde puzzel of een mooi vraagstuk gevonden en wil je die met ons delen? Post het hier.
Plaats reactie
Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

voetbalstickers (deel 2)

Bericht door wnvl » 23 feb 2012, 00:10

Een mooie niet evidente uitbreiding voor gevorderden van voetbalstickers

Bij elke aankoop van een pak koekjes krijg je 1 sticker van een voetballer die je in een album kan plakken.
In totaal zijn er 100 verschillende stickers (die allemaal evenveel voorkomen). Ik plak de stickers in mijn album, maar als ik een sticker al heb, geef ik hem door aan mijn broertje die ook een album heeft. Wat is het gemiddeld aantal stickers dat mijn broertje heeft in zijn album op het ogenblik dat mijn album vol is?
Laatst gewijzigd door wnvl op 23 feb 2012, 01:02, 3 keer totaal gewijzigd.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: voetbalstickers (deel 2)

Bericht door David » 23 feb 2012, 00:44

Jij hebt er naar verwachting 519 (zie het topic waarnaar je verwijst). Hij houdt er honderd zelf en geeft er 419 door. Of bedoel je het aantal verschillende plaatjes? In dat geval denk ik voor nu aan een soort inverse functie (tabelbasis).
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: voetbalstickers (deel 2)

Bericht door wnvl » 23 feb 2012, 01:04

David schreef:Jij hebt er naar verwachting 519 (zie het topic waarnaar je verwijst). Hij houdt er honderd zelf en geeft er 419 door. Of bedoel je het aantal verschillende plaatjes? In dat geval denk ik voor nu aan een soort inverse functie (tabelbasis).
Het gaat over de (verschillende) stickers die mijn broertje heeft in zijn album. Inverse functie van wat?

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: voetbalstickers (deel 2)

Bericht door David » 23 feb 2012, 01:48

We kunnen nu bepalen hoeveel sticker je naar verwachting moet kopen om (1, )2, 3, 4,... verschillende te krijgen. Nu hebben we 419 stickers. Je zou bijv. in een tabel kunnen kijken bij welk aantal verschillende stickers het verwachte aantal 419 is. Dat aantal zou het verwachte aantal stickers zijn dat je broertje heeft.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: voetbalstickers (deel 2)

Bericht door wnvl » 23 feb 2012, 19:57

David schreef:We kunnen nu bepalen hoeveel sticker je naar verwachting moet kopen om (1, )2, 3, 4,... verschillende te krijgen. Nu hebben we 419 stickers. Je zou bijv. in een tabel kunnen kijken bij welk aantal verschillende stickers het verwachte aantal 419 is. Dat aantal zou het verwachte aantal stickers zijn dat je broertje heeft.
Ik denk dat ik begrijp wat je wil bedoelen. Probleem is echter dat de stickers die ik krijg uniform verdeeld zijn, maar de stickers die mijn broertje krijgt zijn dat niet. Stel dat op een bepaald moment ik sticker 1 al 2 keer gehad heb, maar sticker 100 nog niet. De kans dat mijn broertje de volgende keer dat hij een sticker krijgt, het opnieuw sticker 1 zal zijn (die hij al 1 keer gekregen heeft) is veel groter dan dat het sticker 100 zal zijn. Begrijp je wat ik bedoel?

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: voetbalstickers (deel 2)

Bericht door David » 25 feb 2012, 15:15

Hm, ja, ik snap wat je bedoelt. De kans dat je broertje in de situatie die je beschrijft sticker 100 krijgt, is nu 1/10000. Maar ik weet niet hoe je die kans of/hoe de verhouding tussen de kans op sticker 1 en sticker 100 kan gebruiken.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: voetbalstickers (deel 2)

Bericht door wnvl » 25 feb 2012, 19:27

Ik zal de oplossing hier later plaatsen. Ik ben nog op zoek naar een zo eenvoudig mogelijke oplossing, zonder gebruik te maken van "genererende functies" die het antwoord minder intuitief maken.

sacha
Vast lid
Vast lid
Berichten: 32
Lid geworden op: 31 mei 2011, 21:56

Re: voetbalstickers (deel 2)

Bericht door sacha » 27 feb 2012, 20:16

volgens mij heeft het broertje 99 verschillende stickers omdat hij er 100 minder dan jou heeft,
en je moet gemiddeld 100 stickers kopen om de laatste sticker te hebben!

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: voetbalstickers (deel 2)

Bericht door wnvl » 27 feb 2012, 20:59

sacha schreef:volgens mij heeft het broertje 99 verschillende stickers omdat hij er 100 minder dan jou heeft,
en je moet gemiddeld 100 stickers kopen om de laatste sticker te hebben!
Goede poging, maar hij zal er gemiddeld minder hebben. Probleem is dat de stickers die ik krijg uniform verdeeld zijn (ik krijg er gemiddeld van elke soort evenveel), maar bij mijn broertje gaat de spreiding minder uniform zijn.

Ik probeer het beter uit te leggen. Stel mijn broertje heeft al stickers 1, 2, 3, 4 en 5 in zijn collectie en nog niet 6, 7, ... 100. De kans dat de volgende keer dat hij een kaart krijgt, het opnieuw 1, 2, 3, 4 en 5 zal zijn is groter dan dat het 6, 7, ... 100 zal zijn. Omdat het mogelijk is dat ik zelf nog geen 6, 7, ... 100 heb. In zo een geval moet ik dus al 2 keer 6, 7, ... 100 krijgen voor ik deze sticker aan mijn broertje kan doorgeven...

Ik hoop dat mijn uitleg min of meer duidelijk is...

sacha
Vast lid
Vast lid
Berichten: 32
Lid geworden op: 31 mei 2011, 21:56

Re: voetbalstickers (deel 2)

Bericht door sacha » 27 feb 2012, 21:23

snap ik maar als elke sticker evenveel voorkomt is de kans toch groot dat hij elke sticker wel eens dubbel heeft? als hij er 519 heeft

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: voetbalstickers (deel 2)

Bericht door wnvl » 27 feb 2012, 21:54

De kans is groot dat ik heel wat dubbele stickers heb, op het ogenblik dat ik alle 100 stickers heb, maar gemiddeld zullen er toch minder dan 99 dubbele stickers zijn.

Je kan dit als volgt inzien. Het maximum aantal stickers dat mijn broertje kan hebben is 99. Het is echter evident dat er een kans verschillend van 0 is dat hij er minder dan 99 heeft. Bijgevolg moet het gemiddeld aantal minder dan 99 zijn.

Gebruikersavatar
wnvl
Vergevorderde
Vergevorderde
Berichten: 1490
Lid geworden op: 05 okt 2011, 16:30

Re: voetbalstickers (deel 2)

Bericht door wnvl » 28 feb 2012, 20:25

Hier een voorlopige oplossing voor het raadsel. Als er stappen niet duidelijk zijn wil ik ze altijd verduidelijken. Mijn doel was een zo eenvoudig mogelijke oplossing te vinden voor dit probleem. Voor de laatste stap heb ik nog geen eenvoudige intuitieve probabilistische verklaring gevonden (een algebraische verklaring wel). Als iemand een idee heeft...

In de literatuur wordt dit probleem meestal opgelost met genererende functies. Bijbel op dit vlak is het boek van Flajolet

http://algo.inria.fr/flajolet/Publicati ... combi.html

dat je gratis kan downloaden. Maar deze manier van werken is wat mij betreft verre van intuïtief en niet bruikbaar om te gebruiken in de oplossing van een raadsel voor een breed publiek.

Mooie, maar niet eenvoudige uitbreidingen zijn het geval waarbij alle stickers niet evenveel kans hebben om voor te komen of waar ik meerdere broertjes heb.

Denk je net als ik graag na over dit soort van problemen, google dan zeker eens op "Coupon Collector problems". Er zijn heel wat publicaties op dit vlak.

Code: Selecteer alles

Bij elke aankoop van een pak koekjes krijg je 1 sticker van een voetballer die je in een album kan plakken.
In totaal zijn er 100 verschillende stickers (die allemaal evenveel voorkomen). Ik plak de stickers in mijn album, maar als ik een sticker al heb, geef ik hem door aan mijn broertje die ook een album heeft. Wat is het gemiddeld aantal stickers dat mijn broertje heeft in zijn album op het ogenblik dat mijn album vol is?

Stel

m = aantal verschillende stickers in een album = 100
= gebeurtenis dat mijn broertje sticker k heeft op het ogenblik dat mijn collectie compleet is
= aantal stickers dat mijn broertje heeft als mijn collectie van m stickers compleet is




Stel

= gebeurtenis dat mijn broertje sticker m heeft voor ik sticker i heb





Hieruit volgt



Dit kunnen we nog verder vereenvoudigen tot (zoek nog een probabilistische verklaring)



Voor m=100 levert dit 95 op. Mijn broertje heeft dus gemiddeld 95 stickers op het moment dat mijn album vol is.

Plaats reactie