1
Het trekken van ballen uit een vaas
Combinatorische kansproblemen moeten worden aangepakt met een kansmodel dat bestaat uit een eindige uitkomstenverzameling Ω van gelijkwaarschijnlijke uitkomsten. Dit wil zeggen dat de kans op een eventualiteit A ⊂ Ω wordt vastgelegd als IP (A) = #A . Het probleem is dan #Ω in eerste instantie een geschikte verzameling Ω te vinden. Het blijkt hiertoe vaak handig het toevalsexperiment te interpreteren als het doen van een aantal trekkingen uit een vaas met ballen, of als het blindelings werpen van een aantal ballen in een aantal dozen. We bespreken eerst de verschillende manieren waarop ballen uit een vaas getrokken kunnen worden. Uitgangspunt is een vaas met m genummerde ballen waaruit we blindelings n keer een bal trekken. Dat is dus het toevalsexperiment waarvoor we een geschikt kansmodel willen vastleggen. Elke trekking geeft als resultaat het nummer van de getrokken bal. Dit nummer wordt genoteerd en zal onderdeel uitmaken van de beschrijving van een individuele uitkomst van het gehele experiment. De volgende gevallen kunnen we onderscheiden: Trekken met teruglegging. In dit geval wordt na elke trekking de getrokken bal weer teruggelegd in de vaas alvorens de volgende trekking gedaan wordt. Aan het eind van het experiment beschikken we over n nummers die niet alle verschillend hoeven te zijn, omdat het mogelijk is dat sommige ballen meerdere keren getrokken zijn. Deze collectie van n nummers vormt nu de uitkomst van het toevalsexperiment, maar het is nog niet duidelijk hoeveel verschillende uitkomsten er zijn. We kunnen namelijk de volgorde waarin de ballen getrokken worden wel of niet relevant vinden. Met inachtneming van de volgorde. In dit geval kunnen we spreken over de eerste getrokken bal, de tweede getrokken bal, etcetera. Omdat er bij elke trekking m ballen in de vaas zitten zal een enkele uitkomst ω dan een rij zijn van n nummers, m.a.w. ω = (x1 , x2 , . . . , xn ), met xj het nummer van de j-de getrokken bal, dus xj ∈ {1, 2, . . . , m}. De uitkomstenruimte is nu Ω = {(x1 , x2 , . . . , xn ) : xj ∈ {1, 2, . . . , m}, j = 1, 2, . . . , n}. n We zien onmiddellijk dat in dit geval #Ω = m | · m{z· · · m} = m . Als we van mening zijn n
dat deze uitkomsten gelijkwaarschijnlijk zijn dan ligt ons kansmodel voor dit experiment nu vast: IP (A) = #A . Als voorbeeld kiezen we de volgende eventualiteit, mn A(y1 , y2 , . . . , ym ) := {(x1 , x2 , . . . , xn ) ∈ Ω : #{j : xj = i} = yi , i = 1, 2, . . . , m}. Dus A(y1 , y2 , . . . , ym ) is de eventualiteit dat bal i in totaal yi keer getrokken is. Uiteraard moet gelden y1 + y2 + · · · + ym = n. Dan geldt in het gekozen kansmodel, IP (A(y1 , y2 , . . . , ym )) =
n! 1 . y1 !y2 ! · · · ym ! mn
We noemen dit de Boltzmann-Maxwell statistiek. Volgorde irrelevant. Voor de beschrijving van een enkele uitkomst is nu alleen van belang welke ballen getrokken zijn en hoe vaak. Een enkele uitkomst kan nu beschreven worden als ω = (y1 , y2 , . . . , ym ), met yi het aantal keren dat de bal met nummer i getrokken is. Omdat we n keer een bal trekken moet gelden y1 + y2 + · · · + ym = n, 1
dus de uitkomstenruimte is nu Ω = {(y1 , y2 , . . . , ym ) : yi ∈ IN0 , y1 + y2 + · · · + ym = n}. Als we van mening zijn dat deze uitkomsten gelijkwaarschijnlijk zijn, moeten we #Ω bepalen (anders heeft dit geen zin!), om daarmee weer de kansmaat te kunnen vastleggen. Dit is hier veel lastiger dan in het voorgaande geval. Een slimme aanpak is als volgt. Zet m + n − 1 punten op een rij en plaats blindelings op m − 1 van deze punten een verticale streep. Dit kan op Ã
m+n−1 m−1
!
verschillende manieren. Plaats nu dikke stippen op de punten waar geen strepen zijn gezet. Het is nu niet moeilijk het resultaat te interpreteren als een uitkomst ω: het aantal stippen tussen de (i − 1)-ste streep en de i-de streep lezen we als yi , dus het aantal keren dat bal i getrokken is. • · · •} | |• ·{z · · •} | · · · · · · | •| ·{z · · •} | ·{z y1
y2
ym
We krijgen nu als kansmaat IP (A) = Ã
#A !. m+n−1 m−1
Merk op dat de hierboven gedefinieerde eventualiteit A(y1 , y2 , . . . , ym ) in dit kansmodel de singleton-eventualiteit {(y1 , y2 , . . . , ym )} is. Dus in het onderhavige model waarin de volgorde irrelevant wordt verklaard krijgen we IP (A(y1 , y2 , . . . , ym )) = Ã
1 !. m+n−1 m−1
We spreken van de Bose-Einstein statistiek. Trekken zonder teruglegging. Nu worden de getrokken ballen niet teruggelegd in de vaas. Uiteraard moet nu gelden n ≤ m. Ook voor deze situatie kunnen we weer onderscheid maken tussen wel of niet letten op de volgorde. Met inachtneming van de volgorde. Een enkele uitkomst is dan weer te beschrijven als een rij ω = (x1 , x2 , . . . , xn ), met xj het nummer van de j-de getrokken bal. Omdat de ballen nu niet teruggelegd worden, geldt dat de xj ’s alle verschillend zijn. Dus de uitkomstenruimte is Ω = {(x1 , x2 , . . . , xn ) : xj ∈ {1, 2, . . . , m}, j = 1, 2, . . . , n; xj 6= xk voor j 6= k}. Het is nu eenvoudig in te zien dat #Ω = m · (m − 1) · · · · · (m − n + 1), ofwel Ã
2
m n
!
n!
Volgorde irrelevant. Nu is een uitkomst een ongeordende verzameling bestaande uit n verschillende getallen. We kunnen deze verzameling wel als een rij noteren door de getallen uit deze verzameling naar opklimmende grootte op te schrijven. Ω = {(x1 , x2 , . . . , xn ) : xj ∈ {1, 2, . . . , m}, j = 1, 2, . . . , n; x1 < x2 < · · · < xn }. Uiteraard geldt nu
Ã
#Ω =
2
m n
!
.
Het werpen van ballen in dozen
Het uitgangspunt is nu dat we n ballen blindelings werpen in m dozen. We onderscheiden in totaal weer 4 gevallen. Meerdere ballen in een doos toegstaan. Dit is equivalent met het trekken van n ballen met teruglegging uit een vaas van m ballen [het getrokken nummer van de bal is nu het nummer van de doos waarin de bal terechtkomt!] Ballen onderscheidbaar. Dit komt overeen met het inachtnemen van de volgorde bij het trekken van ballen uit een vaas. Dus Ω = {(x1 , x2 , . . . , xn ) : xj ∈ {1, 2, . . . , m}, j = 1, 2, . . . , n}, met nu xj het nummer van de doos waarin bal j terechtkomt. Uiteraard #Ω = mn . Ballen ononderscheidbaar. Dit komt neer op het irrelevant verklaren van de volgorde bij het trekkken van ballen uit een vaas. Dus Ω = {(y1 , y2 , . . . , ym ) : yi ∈ IN0 , y1 + y2 + · · · + ym = n}, Ã
met nu yi het aantal ballen dat in doos i terechtkomt. Uiteraard #Ω =
m+n−1 m−1
!
.
In elke doos hoogstens ´ e´ en bal. Dit is equivalent met het trekken van n ballen uit een vaas met m ballen zonder teruglegging, dus nu weer n ≤ m. Ballen onderscheidbaar. Dit komt overeen met het inachtnemen van de volgorde bij het trekken van ballen uit een vaas. Dus Ω = {(x1 , x2 , . . . , xn ) : xj ∈ {1, 2, . . . , m}, j = 1, 2, . . . , n; xj 6= xk voor j 6= k}, Ã
met nu xj het nummer van de doos waarin bal j terechtkomt. #Ω =
m n
!
n!.
Ballen ononderscheidbaar. Dit komt neer op het irrelevant verklaren van de volgorde bij het trekkken van ballen uit een vaas. Dus Ω = {(x1 , x2 , . . . , xn ) : xj ∈ {1, 2, . . . , m}, j = 1, 2, . . . , n; x1 < x2 < · · · < xn }, Ã
met weer xj het nummer van de doos waar een bal is terechtgekomen. #Ω =
3
m n
!
.
3
Enkele opgaven 1. Uit een vaas met 7 rode en 5 blauwe ballen worden 4 ballen getrokken. Bereken de kansen op onderstaande eventualiteiten. Geef telkens zowel het antwoord voor trekken met als voor trekken zonder teruglegging. (a) De eerste twee ballen zijn rood en de laatste twee zijn blauw, (b) Precies twee ballen zijn rood, (c) De eerste bal en de laatste bal hebben dezelfde kleur. 2. Men vangt in een meer 100 forellen die men merkt en weer teruggooit. Vervolgens vangt men opnieuw 10 forellen, waarvan er 7 gemerkt blijken te zijn. Wat is de kans hierop als er in totaal n forellen in het meer leven? 3. In een machine zijn 3 verschillende typen schroeven gebruikt. Van elk type zeer veel. Er ontbreken twee schroeven waardoor de machine niet meer werkt. Iemand geeft jou drie schroeven, van elk type ´e´en. Wat is de kans dat je nu de machine kunt repareren? 4. Men gooit ´e´en keer met 6 zuivere dobbelstenen. Wat is de kans dat men drie verschillende paren gooit? 5. Men gooit n ballen in n genummerde dozen. Wat is de kans dat precies ´e´en doos leeg blijft? Behandel zowel het geval van onderscheidbare als het geval van ononderscheidbare ballen. 6. De Poolse wiskundige Banach rookte veel en had daarom altijd twee doosjes lucifers bij zich, ´e´en in zijn linkerzak, en ´e´en in zijn rechterzak. Een nieuw doosje bevat n lucifers. Voor elke sigaret graaide hij blindelings in een zak, pakte het doosje, nam een lucifer, en stopte het doosje na gebruik altijd weer in dezelfde zak terug. Als vlak voor het aansteken van een volgende sigaret bleek dat een doosje leeg was, gooide hij beide doosjes weg en stopte twee nieuwe doosjes in zijn beide zakken. Wat is de kans dat bij het weggooien van de beide doosjes k ongebruikte lucifers worden weggegooid? 7. In het vakantiedorp Hadimassa worden toeristen gezien als ononderscheidbare wezens. Er zijn in Hadimassa 20 hotels. Wat is de kans dat de eerste 30 toeristen die aankomen zich z´o over de hotels verspreiden dat er geen enkel hotel leeg blijft? Hoe luidt het antwoord op deze vraag voor het vakantieoord Exclusief, waar ook 20 hotels staan en 30 individueel te onderscheiden toeristen arriveren? 8. Stel dat n onderscheidbare ballen blindelings in m genummerde dozen worden gegooid. Wat is de kans dat er precies k ballen in doos 1 terechtkomen? 9. Als in een kamer zich n personen bevinden, wat is dan de kans dat geen enkel tweetal zijn/haar verjaardag op dezelfde dag viert?
10. Vera en Shimrit doen mee aan een tennistoernooi met in totaal n deelnemers. Alle spelers zijn even sterk en er wordt zoals gebruikelijk bij tennis een ‘afvalsysteem’ gespeeld tot de winnaar overblijft. Voor elke ronde wordt geloot voor het vaststellen van de paring. Wat is de kans dat Vera en Shimrit tegen elkaar zullen spelen? 11. Bij poker ontvangt een speler 5 kaarten uit een pak van 52. Een ‘full house’ bestaat uit 3 kaarten van dezelfde soort en twee kaarten van dezelfde soort (bv. 3 Queens en 2 Achten). Wat is de kans dat je een full house krijgt?
4
12. Een groep van 40 sportlieden, bestaande uit 20 Rotterdammers en 20 Amsterdammers, moet voor een toernooi worden ondergebracht in 20 tweepersoonskamers. Men doet dit blindelings. Wat is de kans dat geen enkele Rotterdammer zijn kamer moet delen met een Amsterdammer? Wat is de kans dat er 2i ‘gemengde’ paren ontstaan (i = 1, 2, . . . , 10)? 13. Een groep van 10 echtparen neemt blindelings plaats aan een ronde tafel. Wat is de kans dat niemand naast zijn/haar eigen echtgeno(o)t(e) zit? 14. Acht torens worden blindelings op een schaakbord geplaatst. Bereken de kans dat geen enkel tweetal elkaar kan slaan. 15. Twee zuivere dobbelstenen worden net zolang geworpen totdat 5 ogen of 7 ogen verschijnen. Bereken de kans dat 5 ogen als eerste verschijnen. 16. Een vaas bevat 3 rode en 7 blauwe ballen. Twee spelers A en B trekken beurtelings zonder teruglegging een bal uit de vaas totdat een rode bal getrokken wordt. A begint. Wat is de kans dat A de eerste rode bal trekt? 17. Uit een verzameling van 8 paren schoenen worden blindelings 6 schoenen getrokken. Wat is de kans dat er minstens ´e´en paar bij zit? Wat is de kans dat er niet een linker- `en een rechterschoen bij zit? Wat is de kans dat er precies twee paren getrokken worden? 18. Bereken de kans dat een bridge-hand van 13 kaarten de King en de Aas van eenzelfde kleur bevat. Bereken ook de kans dat een bridge-hand van minstens ´e´en van de 13 waarden (2,3,. . . ,10,J,Q,K,A) alle kleuren bevat. 19. Men stopt blindelings 10 verschillende foto’s in zes verschillende enveloppen. Bereken de kans dat geen enkele envelop leeg blijft. 20. Een verstrooide professor stopt n persoonlijke brieven in n nog ongeadresseerde enveloppen. Vervolgens schrijft hij lukraak de adressen op de enveloppen. Bereken de kans dat exact k geadresseerden de juiste brief ontvangen. 21. Men gooit n keer met een zuivere munt. Bereken de kans dat in de n worpen niet twee of meer keer achter elkaar ‘kruis’ gegooid wordt. 22. Bij de Lotto worden blindelings 6 verschillende getallen getrokken uit de verzameling {1, 2, . . . , 49}. Bereken de kans dat een 6-tal getrokken wordt met minstens twee elkaar opvolgende getallen. 23. Gegeven is een vaas met N genummerde ballen. We trekken n keer een bal uit de vaas met teruglegging. We zijn ge¨ınteresseerd in het aantal verschillende nummers dat getrokken wordt. Bereken de kans dat m verschillende nummers getrokken worden. 24. (Het Dating Probleem) Elisa wil door middel van ‘daten’ een keuze maken uit n potenti¨ele levenspartners, van wie zij van tevoren niets weet. Na elke ‘date’ weet zij of de laatste partner beter of slechter is dan de eerder ontmoete partners. Als de laatste ‘date’ de beste is tot nu toe, dan moet zij onherroepelijk beslissen of zij de laatste partner accepteert of niet. Dus, zodra zij besluit tot een ‘date’ met een volgende partner, kan zij niet meer op haar schreden terugkeren; de eens afgewezen partner is niet meer beschikbaar. Elisa gaat als volgt te werk: zij besluit tot een ‘date’ met m verschillende partners, die zij geen van allen kiest; vervolgens gaat zij door met ‘daten’ totdat zij iemand gevonden heeft die beter is dan de beste onder de eerste m [reeds afgewezen] partners. Deze partner wordt gekozen. Als zij geen enkele partner meer vindt die beter is dan de beste van de eerste m afgewezen partners dan stort zij zich volledig op haar studie econometrie. De vraag is wat de kans is dat zij via deze zogenaamde m-strategie de beste van de n partners kiest. Bepaal ook de waarde van m waarvoor deze ‘succeskans’ maximaal is. 5
4
Oplossingen 1. Nummer de ballen V = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Laat de nummers 1 t/m 7 de rode ballen zijn en de nummers 8 t/m 12 de blauwe. Het toevalsexperiment is nu: ‘Achtereenvolgens vier genummerde ballen trekken uit V ’. Laat Ri en Bi staan voor de eventualiteiten ‘i-de getrokken bal rood’, resp. ‘i-de getrokken bal blauw’. Vanwege de vragen moeten we de volgorde inachtnemen. We onderscheiden nu de gevallen met en zonder teruglegging. I: met teruglegging. Dan is de uitkomstenruimte met de bijbehorende kansmaat #Ω = 124 , IP (A) =
Ω = {(x1 , x2 , x3 , x4 ) : xi ∈ V },
#A . 124
II: zonder teruglegging. Nu is de uitkomstenruimte met de bijbehorende kansmaat Ω = {(x1 , x2 , x3 , x4 ) : xi ∈ V, xi 6= xj voor i 6= j}, #Ω = 12·11·10·9, IP (A) =
#A . 12 · 11 · 10 · 9
We kunnen nu de vragen beantwoorden. We krijgen steeds twee uitkomsten (voor geval I en voor geval II). (a) I: IP (R1 ∩ R2 ∩ B3 ∩ B4 ) =
1225 7·7·5·5 = . 4 12 20736
II: IP (R1 ∩ R2 ∩ B3 ∩ B4 ) =
7 7·6·5·4 = . 12 · 11 · 10 · 9 99
(b) Ã
I: IP (precies twee rood) =
4 2
!
Ã
II: IP (precies twee rood) =
1225 1225 = . 20736 3456
4 2
!
7 14 = . 99 33
(c) I: IP (eerste en laatste gelijke kleur) = IP (R1 ∩ R4 ) + IP (B1 ∩ B4 ) = 37 7 · 12 · 12 · 7 + 5 · 12 · 12 · 5 = . 4 12 72 II: IP (eerste en laatste gelijke kleur) = IP (R1 ∩ R4 ) + IP (B1 ∩ B4 ) = IP (R1 ∩R2 ∩R3 ∩R4 )+IP (R1 ∩R2 ∩B3 ∩R4 )+IP (R1 ∩B2 ∩R3 ∩R4 )+IP (R1 ∩B2 ∩B3 ∩R4 ) +IP (B1 ∩R2 ∩R3 ∩B4 )+IP (B1 ∩R2 ∩B3 ∩B4 )+IP (B1 ∩B2 ∩R3 ∩B4 )+IP (B1 ∩B2 ∩B3 ∩B4 ) = 7·6·5·4+7·6·5·5+7·5·6·5+7·5·4·6+5·7·6·4+5·7·4·3+5·4·7·3+5·4·3·2 . 12 · 11 · 10 · 9
2. Nummer de gemerkte forellen 1 t/m 100 en de overige van 101 t/m n. Als uitkomstenruimte nemen we Ã
Ω = {(x1 , x2 , . . . , x9 , x10 ) : x1 < x2 < · · · < x9 < x10 }, #Ω =
6
n 10
!
, IP (A) = Ã
#A !. n 10
Merk op dat we hier niet op de volgorde letten, maar we schrijven wel de uitkomsten op naar opklimmend nummer. Nu geldt Ã
IP (7 van de gevangen 10 forellen gemerkt) =
100 7
!Ã Ã
n − 100 3
n 10
!
.
!
3. We kunnen hier onderscheid maken tussen onderscheidbare schroeven en ononderscheidbare schroeven. In het eerste geval is de gevraagde kans 2/3 en in het tweede geval 1/2 [ga dit zelf na]. 4. De uitkomstenrumte met bijbehorende homogene kansnmaat is Ω = {1, 2, 3, 4, 5, 6}6 ,
#Ω = 66 ,
IP (A) =
#A . 66
Om de vraag te kunnen beantwoorden fixeren we eerst een specifiek drietal paren, bv. (1, 1), Ã ! 6 (2, 2) en (3, 3). In totaal zijn er van deze keuzes. We moeten nu de verschillende 3 ‘plaatsen’, aanwijzen voor de enen, de twee-en en de drie-en. Er zijn hievoor in totaal Ã
6 2
!Ã
!Ã
4 2
2 2
!
verschillende mogelijkheden. Alles samengevattend krijgen we de volgende gevraagde kans, Ã Ã
IP (drie verschillende paren) =
6 3
!
6 2
!Ã
4 2 66
!Ã
2 2
!
=
25 . 648
5. Als de ballen onderscheidbaar zijn krijgen we de uitkomstenruimte Ω = {(x1 , x2 , . . . , xn ) : xi is het nummer van de doos waarin bal i terecht komt}. Dus, zoals nu bekend, #Ω = nn en IP (A) = #A . Laat Li de eventualiteit zijn ‘alleen doos i nn blijft leeg’. Dan zijn de verschillende eventualiteiten Li paarsgewijs disjunct, en dus IP (precies ´e´en doos blijft leeg) = IP (L1 ∪ L2 ∪ · · · ∪ Ln ) =
n X
IP (Li ) = nIP (L1 ).
i=1
We hoeven dus alleen IP (L1 ) te berekenen. Hiertoe moeten we het aantal verschillende uitkomsten bepalen waarvoor doos 1 leeg blijft, in ´e´en andere doos twee ballen terechtkomen en in alle overige dozen precies ´e´en bal. Dit aantal is gelijk aan [ga dit zelf na] Ã
n 2
!
(n − 1)(n − 2)!
Alles samenvattend krijgen we, Ã
IP (precies ´e´en doos blijft leeg) = n
7
n 2
!
(n − 1)(n − 2)! nn
Ã
=
n 2
!
n! . nn
Vervolgens bekijken we het geval van ononderscheidbare ballen. Nu is zoals bekend Ω = {(y1 , y2 , . . . , yn ) : yi ∈ IN0 , y1 + y2 + · · · + yn = n}, Ã
!
2n − 1 met yi het aantal ballen dat in doos i terechtkomt. We weten dat #Ω = . De n kansmaat nemen we uiteraard weer homogeen. Als we nu alleen doos 1 leeg willen laten, zijn er slechts n − 1 verschillende uitkomsten, omdat er voor de doos met 2 ballen n − 1 keuzes zijn, en er verder niets meer te kiezen valt omdat in elk van de overige dozen precies ´e´en bal moet komen en de ballen ononderscheidbaar zijn. De lege doos kunnen we weer vari¨eren van doos 1 t/m doos n. Conclusie: n(n − 1) !. IP (precies ´e´en doos blijft leeg) = Ã 2n − 1 n 6. We richten eerst onze aandacht op de eventualiteit Lk dat op het moment dat Banach bij het opsteken van een nieuwe sigaret merkt dat het doosje in zijn rechterzak leeg is er nog k lucifers zitten in het doosje in zijn linkerzak. We vragen ons af wat de ‘kans’ is dat dit optreedt. Hiertoe beschouwen we het toevalsexperiment waarin reeds 2n−k lucifers gebruikt zijn en voor de (2n − k + 1)-ste lucifer een keuze tussen de twee doosjes gemaakt is. Als uitkomstenruimte nemen we Ω = {(x1 , x2 , . . . , x2n−k , x2n−k+1 ) : xi = 0, 1}, #Ω = 22n−k+1 ,
IP ({ω}) =
1 22n−k+1
.
Hier betekent xi = 0 dat de i-de lucifer uit de linkerzak genomen wordt en xi = 1 dat deze uit de rechterzak komt. We kunnen nu de eventualiteit Lk beschrijven als deelverzameling van Ω, Lk = {(x1 , x2 , . . . , x2n−k , x2n−k+1 ) ∈ Ω : x1 + x2 + · · · + x2n−k = n en x2n−k+1 = 1}. We zien nu dat
Ã
!
2n − k n #Lk IP (Lk ) = 2n−k+1 = . 2n−k+1 2 2 Omdat we in het bovenstaande linkerzak en rechtzak vrijelijk kunnen verwisselen, is de gevraagde kans, Ã
IP (er worden k lucifers weggegooid) = 2IP (Lk ) =
2n − k n 2n−k 2
!
.
Merk tenslotte op dat we via dit vraagstuk ongemerkt een wiskundige gelijkheid hebben bewezen via de kansrekening, n X
1
k=0
22n−k
Ã
2n − k n
!
= 1,
wat analytisch misschien wel lastig kan zijn. 7. Omdat de toeristen in Hadimassa als ononderscheidbaar worden beschouwd dringt zich een kansmodel op waarin n = 30 ononderscheidbare ballen in m = 20 dozen worden geworpen. 8
We hanteren daarom de Bose-Einstein statistiek. We weten dan dat het aantal gelijkwaarschijnlijke uitkomsten gelijk is is aan Ã
20 + 30 − 1 20 − 1
!
Ã
=
49 19
!
.
We moeten nu alleen nog het aantal mogelijke uitkomsten tellen waarvoor geen enkele doos (=hotel) leeg is. We zetten eerst in elk hotel ´e´en toerist, Ã !en spreiden de overige 10 (ononder29 scheidbare!) toeristen over de 20 hotels. Dit kan op verschillende manieren. Conclusie: 19 Ã
IP (geen enkel hotel blijft leeg) = Ã
29 19 49 19
! !.
We richten vervolgens onze aandacht op dezelfde vraag voor 30 onderscheidbare toeristen van Exclusief die ook blindelings over 20 hotels verspreid worden. We kunnen de toeristen nu nummeren van 1 t/m 30, en het totale aantal gelijkwaarschijnlijke uitkomsten is nu 2030 . We hebben nu te maken met de Boltzmann-Maxwell statistiek, en we moeten het aantal verschillende verdelingen van de 30 (genummerde) toeristen over de 20 hotels tellen waarin geen enkel hotel leeg blijft. We merken allereerst op dat de eventualiteit ‘geen enkel hotel blijft leeg’ in de eerder ingevoerde notatie kan worden beschreven als [
{A(k1 , k2 , . . . , k20 ) : k1 + k2 + · · · + k20 = 30, ∀i : ki 6= 0}.
Dus de gevraagde kans wordt IP (geen enkel hotel blijft leeg) =
X
30! 20−30 . ki 6=0:k1 +k2 +···+k20 =30 k1 !k2 ! · · · k20 !
U zult het ons niet euvel duiden dat we dit niet verder uitwerken. 8. We hebben hier weer mn verschillende gelijkwaarschijnlijke uitkomsten (x1 , x2 , . . . , xn ) waarbij xj het nummer is van de doos waarin bal j terecht komt. We moeten het aantal uitkomsten à ! n bepalen waarvoor er in doos 1 precies k ballen terechtkomen. Allereerst kunnen we op k verschillende manieren k ballen kiezen voor de bezetting van doos 1. We moeten dan nog de resterende n − k ballen verdelen over de dozen 2 t/m m. Hiervoor zijn uiteraard (m − 1)n−k verschillende mogelijkheden. Samenvattend vinden we Ã
IP (in doos 1 komen precies k ballen terecht) =
n k
!
(m − 1)n−k mn
.
9. We kiezen hier als enkele uitkomst van het toevalsexperiment ‘neem blindelings een groep van n personen’ een rij (x1 , x2 , . . . , xn ) met xj ∈ {1, 2, . . . , 365} de verjaardag van persoon j. Deze uitkomsten verklaren we gelijkwaarschijnlijk. Dus de kans op ´e´en unieke uitkomst is 3651 n (schrikkeljaren laten we buiten beschouwing). We moeten nu het aantal uitkomsten bepalen waarvoor alle verjaardagen verschillend zijn. Dit aantal is gelijk aan 365 · 364 · 363 · · · · · (365 − n + 1), dus de gevraagde kans is IP (geen enkel tweetal op dezelfde dag jarig) =
365 · 364 · 363 · · · · · (365 − n + 1) . 365n
Het is verrassend dat voor n = 23 deze kans al groter is dan een half. Reken dit zelf even na. 9
10. We kiezen voor n een macht van twee, zeg n = 2k , omdat anders niet een ‘volledig’ toernooi is te organiseren. Hoewel we hieronder een ‘slimme’ aanpak zullen bespreken, zullen we eerst voor de gebruikelijke opzet kiezen. We zoeken daartoe een verzameling Ω van individuele gelijkwaarschijnlijke uitkomsten van het volledige toevalsexperiment, d.w.z. het gehele tennistoernooi. Nummer de spelers van 1 t/m n = 2k (1=Shimrit, 2=Vera). We indiceren de van k afhankelijke uitkomstenruimte met k, het aantal ronden in het toernooi. Voor de eenvoud beginnen we met 2 spelers (k = 1). Dan is Ω1 = {{1, 2}}, nogal flauw. Iets aardiger wordt het al voor n = 4 (k = 2), Ω2 = {({x, y}, {{x, u}, {y, v}}) : x, y, u, v ∈ {1, 2, 3, 4}, alle verschillend }. Hier staat {x, y} voor een finalepartij en {{x, u}, {y, v}} voor twee partijen uit de eerste ! Ã 4 2 = 12. Omdat alle individuele uitkomsten als gelijkronde. We zien dat #Ω2 = 2 waarschijnlijk te beschouwen zijn vanwege de gegevens over de sterkte van de spelers, is de gevraagde kans nu uit te rekenen door het aantal uitkomsten te tellen waarin speler 1 en 2 elkaar ontmoeten. Dit is mogelijk in de finale (2 uitkomsten) of in de eerste ronde (4 uitkomsten), in totaal 6. Conclusie 1 en 2 ontmoeten elkaar met kans 6/12=1/2. We voeren nu dezelfde exercitie uit voor 8 spelers (k = 3), Ω3 = {({x, y}, {{x, u}, {y, v}}, {{x, p}, {u, q}, {y, r}, {v, s}}) : x, y, u, v, p, q, r, s verschillend }. Hier staat {x, y} weer voor een finalepartij, {{x, u}, {y, v}} voor twee partijen uit de tweede ronde en {{x, p}, {u, q}, {y, r}, {v, s}} voor vier partijen uit de eerste ronde. Nu geldt Ã
#Ω3 =
8 2
!Ã
6 2
!
Ã
(2!)
4 4
!
1 (4!) = 8!. 2
We kunnen nu wel vermoeden hoe we in het algemene geval Ωk moeten beschrijven (zullen we niet uitspellen) en tevens hoe het aantal elementen van Ωk berekend kan worden, Ã
#Ωk =
2k 2
!Ã
2k − 2 2
!
Ã
(2!)
2k − 4 4
!
Ã
(4!) · · ·
2k − 2i 2i
!
à i
(2 !) · · ·
2k−1 2k−1
!
1 (2k−1 !) = n!, 2
voorwaar een verrassend eenvoudig antwoord! [hadden we dit misschien ook sneller kunnen inzien?] We kunnen nu overgaan tot de berekening van de gevraagde kans door het aantal uitkomsten à !te tellen waarin speler 1 en 2 elkaar ontmoeten. Omdat er voor elke specifieke n partij verschillende mogelijkheden zijn perken we het totale aantal mogelijke toer2 à ! n nooien (uitkomsten) in met een factor als we eisen dat speler 1 en 2 in een specifieke 2 1
n! partij tegen elkaar moeten spelen. Dit geeft dus à 2 ! verschillende uitkomsten met een n 2 partij tuseen 1 en 2 op een specifieke plaats. Verder weten we dat er in totaal n − 1 partijen gespeeld worden (er zijn dus n − 1 specifieke partijen). Samenvattend krijgen we 1
à 2 n! !
n 2 IP (Vera en Shimrit ontmoeten elkaar) = (n − 1) 1 n! 2
=
1 1 n 2
=
1 2k−1
.
We vragen ons nu af of we dit eenvoudige antwoord ook langs een andere weg hadden kunnen vinden. Het antwoord is ja, en de aanzet voor een simpele aanpak ligt al besloten in het 10
Ã
!
n bovenstaande. We richten ons eerst op de finale-partij. Uiteraard zijn er verschillende 2 finales mogelijk. Vanwege de onderlinge sterkte van de spelers zijn deze finale-partijen gelijkwaarschijnlijk. Dus de kans dat speler 1 en 2 elkaar ontmoeten in de finale is à 1 ! . Het n 2 aardige is nu dat deze redenering ook opgaat voor elke specifieke partij uit het toernooi (bv. de ‘vijfde partij uit de achtste finales’, om maar wat te noemen). Nummer nu alle partijen van 1 t/m n − 1 (bv partij 1 is de finale, 2 de eerste halve finale, 3 de tweede halve finale, etcetera) en definieer Qj als de eventualiteit ‘Vera en Shimrit ontmoeten elkaar in partij j’. Omdat de Qj ’s paarsgewijs disjunct zijn geldt dan IP (Vera en Shimrit ontmoeten elkaar) = IP (Q1 ∪ Q2 ∪ · · · ∪ Qn−1 ) = n−1 1 1 IP (Q1 ) + IP (Q2 ) + · · · + IP (Qn−1 ) = à ! = 1 = k−1 . 2 n n 2 2 Tenslotte bekijken we nog een recursieve aanpak. Laat Pk de gevraagde kans zijn voor een toernooi met n = 2k spelers. Dus P1 = 1. Dan is het niet moeilijk in te zien dat geldt µ ¶2
Pk =
1 2k − 2 1 + 2k − 1 2k − 1 2
Pk−1 .
We merken wel op dat hierbij op een nogal intu¨ıtieve manier van conditionering gebruik gemaakt is. De rechterkant moet men lezen als ‘Vera en Shimrit ontmoeten elkaar in de eerste ronde en zo niet, dan moeten ze beiden in de eerste ronde winnen en elkaar later ontmoeten’. Dit is natuurlijk een ingewikkelde manier om te zeggen dat ze elkaar ergens zullen ontmoeten en daarmee is de gegeven recursie ‘aangetoond’. We grijpen dit vraagstuk ook aan om de vraag te beantwoorden ‘hoeveel verschillende partijen in de eerste ronde gespeeld kunnen worden’. We geven twee formules. Het eenvoudigst is te beginnen met speler 1 en vast te stellen dat er voor deze speler n − 1 mogelijke tegenstanders zijn. Dan blijven er n − 2 spelers over die nog gepaard moeten worden. Kies er ´e´en uit en stel vast dat voor deze spelers nog n − 3 tegenstanders mogelijk zijn. We vinden zo, Aantal verschillende paringen van n spelers = (n − 1)(n − 3) · · · · · 5 · 3 · 1. We kunnen ook als volgt te werk gaan: zet alle spelers op een rij. Dit geeft n! verschillende rijen spelers. Verklaar nu de eerste twee tot een paar, de derde en de vierde, etcetera. Zo krijgen we een geordende rij van 21 n geordende paren. Om tot het gevraagde aantal paringen te komen moeten we nu de ordening uit de paren zelf halen en ook uit de ordening tussen de paren onderling. Zo vinden we Aantal verschillende paringen van n spelers =
n! (2!)
n 2
³ ´ . n 2
!
11. Het toevalsexperiment is hier het blindelings trekken van 5 kaarten zonder teruglegging uit een pak van 52 kaarten, waarbij de volgorde irrelevant is. Een enkele uitkomst is dan te noteren als een vijftupel (x1 , x2 , x3Ã, x4 , x!5 ) met x1 < x2 < x3 < x4 < x5 [de volgorde is alleen 52 een kwestie van notatie!]. Er zijn verschillende gelijkwaarschijnlijke uitkomsten. We 5 moeten daarom de vraag weer beantwoorden door het aantal verschillende uitkomsten te bepalen die een ‘full house’ geven. We beginnen met het kiezen van twee soorten, ´e´en voor 11
het drietal van dezelfde soort e´en voor het tweetal. Dit geeft 13 · 12 mogelijkheden. Bij à en!´ 4 elk van deze keuzes zijn er verschillende mogelijkheden voor een specifiek drietal en 3 à ! 4 verschillende mogelijkheden voor een specifiek tweetal. Alles samenvattend vinden we 2 Ã
13 · 12 IP (pokerspeler ontvangt een ‘full house’) =
Ã
4 3 52 5
!Ã !
4 2
!
.
12. Het toevalsexperiment is in dit geval het blindelings verdelen van de 40 sportlieden in paren. We hebben bij vraagstuk 10 (tennistoernooi) gezien dat het aantal verschillende uitkomsten gelijk is aan 22040!20! . Vervolgens moeten we het aantal mogelijkheden bepalen waarin alle Amsterdammers met elkaar gepaard worden (dan worden automatisch ook alle Rotterdammers ³ ´2 met elkaar gepaard). Dit aantal is gelijk aan 21020!10! omdat elke combinatie van een paring van de Amsterdammers met een paring van de Rotterdammers een totale paring zonder ‘gemengde’ paren geeft. Dus ³
IP (geen gemengde paren) =
20!
´2
210 10! 40! 220 20!
=
(20!)3 . (10!)2 40!
We tellen nu het à aantal ! paringen waarbij precies 2i ‘gemengde’ paren voorkomen. Allereerst 20 kunnen we op verschillende mannieren 2i Amsterdammers kiezen uit de groep van 2i 20 Idem voor een groep van 2i Rotterdammers. In totaal zijn er daarom à Amsterdammers. !à ! 20 20 (2i)! verschillende mogelijkheden om 2i gemengde paren te maken. Bij elke 2i 2i keuze voor 2i gemengde paren moeten nu de resterende 20 − 2i Amsterdammers en 20 − 2i h i2 (20−2i)! Rotterdammers nog ‘ongemengd’ gepaard worden. Dit kan op 210−i (10−i)! verschillende manieren. Samenvattend krijgen we, Ã
IP (er treden precies 2i gemengde paren op) =
20 2i
!2
(2i)!
h
(20−2i)!
i2
210−i (10−i)!
40! 220 20!
.
13. Dit vraagstuk kunnen we het beste aanpakken met de ‘inclusie-exclusie’ formule. Nummer de echtparen 1 t/m 10, en laat Ei de eventualiteit zijn dat de beide echtelieden van echtpaar i naast elkaar zitten. Als we de 20 stoelen niet nummeren dan zijn er in totaal 19! verschillende mogelijkheden om de personen aan de tafel te laten plaatsnemen (ga na), die we als gelijkwaarschijnlijk zullen beschouwen. M.a.w. elke precieze tafelschikking heeft een 1 op realisatie. Met bovenstaande notatie kunnen we nu de kans waarin we zijn kans van 19! ge¨ınteresseerd met behulp van de wet van DeMorgan schrijven als c ) = 1 − IP (E1 ∪ E2 ∪ · · · ∪ E10 ). IP (E1c ∩ E2c ∩ · · · ∩ E10
We herhalen nog even de algemene ‘inclusie-exclusie’ regel, IP (E1 ∪ E2 ∪ · · · ∪ En ) =
n X i=1
IP (Ei ) −
X i<j
12
IP (Ei ∩ Ej ) +
X i<j
IP (Ei ∩ Ej ∩ Ek ) − · · ·
· · · + (−1)n+1 IP (E1 ∩ E2 ∩ · · · ∩ En ). We zien nu dat het voldoende is de kansen IP (Ei ), IP (Ei ∩ Ej ), etcetera te berekenen. Dit is niet zo moeilijk omdat deze kansen vanwege symmetrie-argumenten niet afhangen van de specifieke echtparen. Bijvoorbeeld IP (Ei ) = 2·18! . We zien dit als volgt: vat (voor 19! het moment) echtpaar i op als ´e´en ‘persoon’ die samen met de overgebleven 18 personen blindelings rond de tafel gezet worden (18! mogelijkheden); merk vervolgens op dat het echtpaar op twee manieren kan plaats nemen (vrouw links of rechts van man). Nog een voorbeeld: IP (Ei ∩ Ej ) = 4·17! . Vat de twee echtparen i en j even op als twee ‘personen’ 19! die we samen met de overige 16 individuele personen rond de tafel plaatsen; dit geeft 17! mogelijkheden; verder zijn er 22 = 4 verschillende manieren waarop de echtelieden (van de echtparen i en j) onderling kunnen worden neergezet. Nu algemeen, IP (Ei1 ∩ Ei2 ∩ · · · ∩ Eik ) =
2k (19 − k)! . 19!
We redeneren weer als hierboven: vat de k echtparen even op als k ‘personen’ die samen met de 20 − 2k overgebleven individuele personen rond de tafel gezet worden. Dit kan op (k + 20 − 2k − 1)! = (19 − k)! verschillende manieren. Tenslotte zijn er voor de k echtparen nog 2k mogelijkheden omdat bij elk van deze echtparen de man links of rechts van zijn vrouw kan zitten. Alles samenvattend krijgen we het volgende resultaat, IP (E1 ∪ E2 ∪ · · · ∪ E10 ) =
10 X
à k+1
(−1)
k=1
10 k
!
2k
(19 − k)! ≈ 0.7344. 19!
Dus de gevraagde kans is 0.2656. 14. Het is handig de torens te nummeren van 1 t/m 8. We plaatsen nu de torensÃachter!elkaar op 64 8! gelijkhet bord, eerst toren 1, etcetera. Hiervoor zijn in totaal 64 · 63 · 62 · · · 57 = 8 waarschijnlijke mogelijkheden. We hebben hiermee gekozen voor een model van ‘8 ballen trekken uit een vaas met 64 ballen zonder teruglegging met inachtneming van de volgorde’. Dus Ω = {(x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 ) : xi ∈ {1, 2, . . . , 64}, xi 6= xj voor i 6= j}. We moeten nu het aantal uitkomsten tellen waarvoor geen enkele toren een andere kan slaan. We redeneren als volgt: voor de eerste toren zijn er 64 mogelijkheden, voor de tweede toren 64−1−14 = 49, voor de derde toren 49−1−14+2 = 36, etcetera. Algemeen, laat tk het aantal resterende mogelijkheden zijn voor de k-de toren. Dan geldt tk+1 = tk − 1 − 14 + 2(k − 1), zoals eenvoudig is na te gaan [maak een plaatje!]. De gevraagde kans wordt nu IP (acht blindelings geplaatste torens kunnen elkaar niet slaan) =
64 · 49 · 36 · 25 · 16 · 9 · 4 · 1 . 64 · 63 · 62 · 61 · 60 · 59 · 58 · 57
Het is illustratief dit probleem ook op te lossen met zogenaamd ‘ononderscheidbare’ torens. Dit komt erop neer dat we de ‘ballen à !uit de vaas trekken zonder teruglegging zonder op de 64 volgorde te letten. Er zijn dan verschillende gelijkwaarschijnlijke mogelijkheden, nl. 8 Ω = {(x1 , x2 , x3 , x4 , x5 , x6 , x7 , x8 ) : xi ∈ {1, 2, . . . , 64}, x1 < x2 · · · < x8 }. Merk weer op dat we een uitkomst wel noteren naar opklimmend nummer, maar dat hier niet op de volgorde gelet wordt. We gaan nu weer het aantal mogelijkheden tellen waarbij geen enkel tweetal torens elkaar kan slaan. Als we de velden van het schaakbord nummeren van 13
boven naar beneden (bovenste rij 1 t/m 8, tweede rij 9 t/m 16, etc.), dan zien we dat moet gelden x1 ≤ 8 [er moet een toren op de bovenste rij geplaatst worden], dus 8 mogelijkheden. voor de tweede rij moet gelden x2 6= x1 + 8 [ga na], dus nog 7 mogelijkheden. Zo doorgaande vinden we 8! mogelijkheden en de gevraagde kans wordt nu à 8! ! , uiteraard hetzelfde getal 64 8 als eerder gevonden is via het model waarin wel op de volgorde gelet werd (onderscheidbare, namelijk genummerde torens). 15. Strict genomen kunnen we dit vraagstuk nog niet oplossen, omdat de uitkomstenruimte bij het toevalsexperiment ‘gooi met twee dobbelstenen totdat vijf of zeven ogen verschijnen’ geen eindige uitkomstenruimte heeft [waarom niet?]. Toch kunnen we het probleem wel oplossen door ons te concentreren op de eventualiteit ‘bij de i-de worp met de twee stenen worden voor het eerst vijf ogen gegooid en in de eerdere worpen noch vijf noch zeven ogen’. We noteren deze eventualiteit met Vi . We kunnen de kans op Vi bepalen door een kansmodel te maken gebaseerd op het toevalsexperiment ‘gooi i keer met de twee dobbelstenen’. Hiervoor geldt (we indiceren de uitkomstenruimte met i) Ωi = {((x1 , y1 ), (x2 , y2 ), . . . , (xi , yi )) : xk , yk ∈ {1, 2, 3, 4, 5, 6}}, waarbij xk en yk het aantal ogen zijn van de eerste resp. tweede dobbelsteen bij de k-de worp (met de twee stenen). Al deze uitkomsten modelleren we als gelijkwaarschijnlijk en er geldt #Ωi = 36i . We kunnen nu IP (Vi ) berekenen door het aantal uitkomsten in Vi te tellen. Voor de aardigheid beschrijven we Vi als deelverzameling van de uitkomstenruimte Ωi , Vi = {((x1 , y1 ), (x2 , y2 ), . . . , (xi , yi )) ∈ Ωi : voor k ≤ i−1, xk +yk 6= 5 & xk +yk 6= 7, xi +yi = 5} Hieruit zien we (bijna) onmiddellijk dat #Vi = 26i−1 · 4, en hiermee dat µ
IP (Vi ) =
13 #Vi 26i−1 · 4 = = i #Ωi 36 18
¶i−1
1 . 9
Nu maken we een op dit moment niet volledig te rechtvaardigen stap, IP (vijf ogen treden eerder op dan zeven ogen) = IP
̰ [
!
∞ X
Vi =
i=1
IP (Vi ).
i=1
Het probleem is dat de kansmaten aan de rechterkant alle gedefinieerd zijn op verschillende toevalsexperimenten (de kansmaten hangen ook van i af, maar dit hebben we niet in de notatie opgenomen), terwijl de kansmaat links niet gedefinieerd is. We hebben zelfs niet vastgesteld hoe het toevalsexperiment (‘gooien totdat vijf of zeven ogen verschijnen’) eruit ziet waarbij deze kansmaat eventueel gedefinieerd zou kunnen worden. Later zullen we zien dat dit allemaal z´o gedaan kan worden dat bovenstaande gelijkheid wiskundig te rechtvaardigen is. We gaan hier nu niet verder op in, en beperken ons tot het berekenen van de gevraagde kans [alsof dit mag zoals we het nu doen!], IP (vijf ogen treden eerder op dan zeven ogen) =
¶ ∞ µ X 13 i−1 1 i=1
18
We hebben hier gebruik gemaakt van de ‘meetkundige reeks’
9
P∞
k=0
=
1 1 2 = . 13 5 1 − 18 9
xk =
1 1−x
voor |x| < 1.
16. Het is duidelijk dat we hier een kansmodel moeten maken voor het toevalsexperiment ‘trekken zonder teruglegging met inachtneming van de volgorde’. Omdat we niet van tevoren weten na hoeveel trekkingen we kunnen stoppen (als de eerste rode bal getrokken wordt), 14
is het handig voor het opzetten van een kansmodel met gelijkwaarschijnlijke uitkomsten te doen alsof alle ballen getrokken worden (dit be¨ınvloedt natuurlijk niet de gevraagde kans). Nummer de rode ballen van 1 t/m 3, en de blauwe ballen van 4 t/m 10. Dan is Ω = {(x1 , . . . , x10 ) : xi ∈ {1, 2, . . . , 10}, xi 6= xj voor i 6= j}, waarbij xi het nummer is van de i-de getrokken bal. Al deze uitkomsten beschouwen we als gelijkwaarschijnlijk en we zien dat #Ω = 10!. Om de gevraagde kans te kunnen berekenen defini¨eren we de eventualiteiten Ri , die staan voor ‘de i-de getrokken bal is de eerste rode bal’. Dan is duidelijk dat IP (A trekt eerste rode bal) = IP (R1 ∪ R3 ∪ R5 ∪ R7 ∪ R9 ) =
5 X
IP (R2j−1 ).
j=1
De laatste gelijkheid volgt omdat de eventualiteiten Ri paarsgewijs disjunct zijn. Het probleem is nu gereduceerd tot het tellen van het aantal uitkomsten in de eventualiteit Ri . We beschrijven voor alle duidelijkheid Ri ook als deelverzameling van Ω, Ri = {(x1 , . . . , x10 ) ∈ Ω : xk ≥ 4 voor k = 1, . . . i − 1, xi ≤ 3}. Het is nu niet moeilijk meer het aantal uitkomsten in Ri te bepalen. #Ri = 7 · 6 · · · (7 − i + 2) · 3 · (10 − i)! =
i−2 Y
(7 − k) · 3 · (10 − i)!.
k=0
Q
We hebben bewust de notatie ‘ ’ voor het product gebruikt omdat, met de conventie dat een leeg product (hier voor i = 1) de waarde 1 heeft, de rechterformule nu algemeen geldig is, terwijl de middelste formule voor i = 1 zonder betekenis is. We krijgen nu, IP (A trekt eerste rode bal) =
5 X
IP (R2j−1 ) =
j=1
5 X
Q2j−3 k=0
j=1
(7 − k) · 3 · (11 − 2j)! = 10!
3 · 9! 7 · 6 · 3 · 7! 7 · 6 · 5 · 4 · 3 · 5! 7 · 6 · 5 · 4 · 3 · 2 · 3 · 3! 7 + + + +0= . 10! 10! 10! 10! 12 Het is leerzaam voor dit probleem ook een aanpak te bespreken waarbij de ballen niet genummerd worden (tenslotte speelt alleen de kleur een rol). We kunnen dan als uitkomstenruimte kiezen Ω = {(x1 , . . . , x10 ) : xi ∈ {0, 1},
10 X
xi = 7},
i=1
waarbij nu xi = 0 betekent dat de i-de getrokken bal rood is, en xi = 1 dat deze blauw is. Omdat in het toevalsexperiment alle ballen getrokken worden kunnen we nu ook opmerken dat de verschillende uitkomsten gelijkwaarschijnlijk beschouwd kunnen worden, maar laat het goed tot je doordringen dat deze aanpak (zonder de ballen te nummeren) niet meer mogelijk à ! 10 is als niet alle ballen getrokken worden (zie bijvoorbeeld opgave 1). Nu geldt #Ω = , 7 omdat we in een rijtje van 10 plaatsen op 7 plaatsen een 1 moeten zetten (overige plaatsen krijgen een 0). We beschrijven nu Ri weer als deel van de nieuwe Ω, Ri = {(x1 , . . . , x10 ) ∈ Ω :
i−1 X k=1
15
xk =
i X k=1
xk = i − 1}.
Ã
!Ã
!Ã
!
10 − i 1 i−1 , te interpreteren als: onder We kunnen nu vaststellen dat #Ri = 0 1 2 de eerste i − 1 xk ’s geen enkele 0, xi = 0, en van de resterende 10 − i xk ’s precies twee 0. Zo vinden we à !à !à ! i−1 1 10 − i 0 1 2 (10 − i)! · 7! · 3! à ! IP (Ri ) = = , 2! · (8 − i)! · 10! 10 7 hetgeen hetzelfde resultaat is als we eerder gevonden hebben, wat onmiddellijk is in te zien als men opmerkt dat i−2 Y 7! = (7 − k). (8 − i)! k=0 17. Nummer de 8 paar schoenen van 1 t/m 16, waarbij de nummers 2k − 1 en 2k het k-de paar representeren. We hebben nu van doen met een toevalsexperiment waarbij zonder teruglegging 6 schoenen uit de collectie gekozen worden. We letten niet op de volgorde, dus zoals gebruikelijk is de uitkomstenruimte met gelijkwaarschijnlijke uitkomsten, Ω = {(x1 , . . . , x6 ) : xi ∈ {1, 2, . . . , 16}, x1 < x2 < · · · < x6 }, Ã
!
16 . Voor het beantwoorden van de eerste vraag defini¨eren we de eventualiteiten en #Ω = 6 Ei : ‘het i-de paar wordt getrokken’. Dan geldt IP (minstens ´e´en paar wordt getrokken) = IP (E1 ∪ E2 ∪ E3 ∪ E4 ∪ E5 ∪ E6 ∪ E7 ∪ E8 ). Omdat de eventualiteiten Ei niet paarsgewijs disjunct zijn moeten we weer de ‘inclusieexclusie’ formule gebruiken (zie ook opgave 13). Omdat de in deze formule voorkomende doorsneden weer niet van de specifieke paren afhangen, kunnen we volstaan de kansen te berekenen voor de eventualiteiten van de vorm Ei1 ∩ Ei2 ∩ · · · ∩ Eik , d.w.z. de kans dat een specifieke collectie van k paren schoenen getrokken wordt (k = 1, 2, 3). Eenvoudig is in te zien dat geldt Ã
IP (Ei1 ∩ Ei2 ∩ · · · ∩ Eik ) =
2k 2k
!Ã Ã
16 − 2k 6 − 2k
16 6
!
!
=
(16 − 2k)! · 6! . (6 − 2k)! · 16!
Hiermee kunnen we de gevraagde kans berekenen (vergelijk ook met opgave 13), IP (E1 ∪ E2 ∪ · · · ∪ E8 ) =
3 X
Ã
(−1)
k+1
k=1
8 k
!
3 1 111 (16 − 2k)! · 6! =1− + = . (6 − 2k)! · 16! 13 143 143
We geven ook een andere aanpak, waarbij we het complement berekenen van de eventualiteit ‘minstens ´e´en paar schoenen wordt getrokken’. Dus we bepalen de kans dat ‘geen enkel paar schoenen wordt getrokken’. We generaliseren het probleem meteen even tot een collectie van n paar schoenen, waaruit 2r schoenen blindelings getrokken worden. Ga na dat nu geldt, Ã
IP (geen enkel paar wordt getrokken) = 22r Ã
16
n 2r 2n 2r
! !,
en merk op dat IP (minstens ´e´en paar wordt getrokken) = 1 − IP (geen enkel paar wordt getrokken). De volgende vraag is eenvoudig omdat ‘niet een linker- `en een rechterschoen’ neerkomt op ‘alle getrokken schoenen linkerschoenen `of alle getrokken schoenen rechterschoenen’. De laatste twee eventualiteiten hebben dezelfde kans en zijn disjunct, dus Ã
!Ã
8 6
IP (niet een linker- `en een rechterschoen) = 2
Ã
8 0
!
=
!
16 6
1 . 143
Tenslotte bepalen we de kans dat precies twee paar schoenen getrokken wordt. We bepalen eerst de kans dat paar 1 en paar 2 getrokken worden en geen enkele van de andere paren, dus Ã
!Ã
4 4
IP (E1 ∩ E2 ∩ E3c ∩ E4c ∩ E5c ∩ E6c ∩ E7c ∩ E8c ) =
6 2
!Ã
Ã
!Ã
2 1
!
16 6
2 1
!
=
15 . 14 · 13 · 11
Toelichting: van de schoenen 1 t/m 4 (paar 1 en 2) moeten alle vier getrokken worden, van de overige 6 paren (3 t/m 8) à moeten ! van twee verschillende paren de resterende twee schoenen 6 getrokken worden; er zijn mogelijkheden om twee paren te kiezen uit de paren 3 t/m 2 à !à ! 2 2 8; bij elke keuze voor een specifiek tweetal paren zijn er mogelijkheden om van 1 1 elk paar ôe´en ! schoen te trekken. Omdat deze kans niet afhangt van de specifieke keuze 1 en 8 2, en er keuzes zijn voor het tweetal paren, krijgen we 2 Ã
IP (precies twee paren getrokken) =
8 2
!
15 30 = . 14 · 13 · 11 143
18. Het toevalsexperiment is hier ‘trek 13 kaarten uit een pak van 52 zonder teruglegging, volgorde irrelevant’. Dus, Ω = {(x1 , . . . , x13 ) : xi ∈ {1, 2, . . . , 52}, x1 < x2 < · · · < x13 }, Ã
!
52 en #Ω = . De beide gevraagde kansen moeten met ‘inclusie-exclusie’ beantwoord 13 worden. We geven de antwoorden zonder verder commentaar [ga zelf de details na!], Ã
4 IP (een Aas en een King van dezelfde kleur) =
Ã
13 IP (van minstens ´e´en waarde alle kleuren) =
17
50 11
48 9
!
Ã
−6
48 9
!
Ã
!
Ã
−
13 2
+4 52 13
!Ã Ã
à !
44 5
52 13
46 7
!
!
Ã
+
!
Ã
−
13 3
44 5
!Ã
!
40 1
= 0.2198.
!
= 0.0342.
19. Laat Ω = {(x1 , . . . , x10 ) : xi ∈ {1, . . . , 6}}, waarbij xi het nummer is van de envelop waarin foto i terecht komt. Hierop beschouwen we uiteraard het homogene model, #Ω = 610 . Laat nu Ej de eventualiteit zijn dat envelop j leeg blijft (j = 1, . . . , 6). Dan kunnen we de vraag formuleren als: bereken IP {E1c ∩ · · · ∩ E6c }. Met De Morgan weten we nu IP
6 \
j=1
c 6 6 [ [ Ejc = IP Ej . Ej = 1 − IP j=1
j=1
We passen vervolgens de algemene somregel toe IP
6 [
j=1
Ej
=
6 X
IP {Ej } −
j=1
X
IP {Ej ∩ Ek } + · · · + (−1)5 IP
6 \
Ej
j=1
j
.
(∗)
Nu geldt op grond van het gekozen (homogene) model IP {Ej } =
#Ej 510 = 10 , #Ω 6
#(Ej ∩ Ek ) 410 = 10 , #Ω 6
IP {Ej ∩ Ek } =
et cetera,
en uiteraard is IP {E1 ∩ · · · ∩ E6 } = 0. We hoevenÃons !er nu alleen nog van te vergewissen dat het 6 aantal termen in de r-de som in (*) gelijk is aan . Alles samenvattend krijgen we r IP
6 \
j=1
Ejc
=1−
5 X
Ã
6 r
r=1
!
(−1)r−1
(6 − r)10 38045 . = 10 6 139968
20. We nummeren zowel de brieven als de adressen van 1 t/m n. Dan is Ω = {(x1 , . . . , xn ) : xi ∈ {1, . . . , n}, xi 6= xj voor i 6= j}, waarbij xi het nummer is van de brief die in de envelop met adres i zit. We kiezen opnieuw voor het homogene model, #Ω = n!. We berekenen nu eerst de kans op de eventualiteit, zeg F , dat de brieven 1 t/m juist geadresseerd zijn en de brieven k + 1 t/m n niet. Dan zal het gevraagde à k! n antwoord zijn IP {F } om redenen van symmetrie. Laat Aj de eventualiteit zijn dat brief j k juist geadresseerd is. Dan hebben we IP {F } = IP
k \
n \
Aj ∩
j=1
Acj
j=k+1
.
Het komt er daarom op neer het aantal rijtjes (1, 2, . . . , k, xk+1 , . . . , xn ) te tellen waarvoor geldt xj 6= j voor j = k + 1, . . . , n. Nu weten we al [blz. 59, example 2.24 in Ghahramani] dat bij het blindelings stoppen van m persoonlijke brieven in m verschillend geadresseerde enveloppen de kans dat geen enkele brief in de juiste envelop terecht komt gelijk is aan m X (−1)r r=2
r!
.
Met andere woorden het aantal rijtjes (y1 , . . . , ym ) van verschillende getallen yi ∈ {1, . . . , m} met yi 6= i voor alle i = 1, . . . , m is gelijk aan m!
m X (−1)r r=2
r!
.
Dit geeft voor het onderhavige probleem [m = n − k] #F = (n − k)!
n−k X r=2
18
(−1)r . r!
Alles samenvattend kunnen we concluderen dat de gevraagde kans gelijk is aan Ã
IP {precies k brieven correct geadresseerd} =
n k
!
(n − k)!
Pn−k (−1)r r=2
r!
n!
=
X (−1)r 1 n−k . k! r=2 r!
21. Zoals we weten is Ω = {0, 1}n [1=‘kruis’, 0=‘munt’]. We kiezen voor het homogene model, en daarmee is het probleem teruggebracht tot het tellen van het aantal rijtjes nullen en enen van lengte n waarin niet twee of meer enen achter elkaar staan [vanaf nu afgekort tot *rijtjes]. Definieer ti als het aantal *rijtjes van lengte i. Dan geldt de volgende recursie voor i = 3, 4 . . . ti = ti−1 + ti−2 , met t1 = 2 en t2 = 3 (ga na). Deze recursie is als volgt in te zien: de *rijtjes van lengte i kunnen we opsplitsen in twee disjuncte groepen: *rijtjes eindigend op een ‘0’ en *rijtjes eindigend op een ‘1’. Het aantal dat eindigt op een ‘0’ is gelijk aan ti−1 , omdat elk *rijtje van lengte i − 1 een *rijtje van lengte i wordt als je een ‘0’ aan het eind toevoegt. Blijft over te bepalen hoeveel *rijtjes van lengte i er zijn die eindigen op een ‘1’. Als je bij zo’n *rijtje de laatste ‘1’ weglaat, krijg je altijd een *rijtje van lengte i − 1 dat op een ‘0’ eindigt (waarom?), en zoals we net gezien hebben is het aantal van dat soort *rijtjes gelijk aan ti−2 ! Hiermee is de bovenstaande recursie aangetoond. Ons probleem is nu teruggebracht tot het berekenen van tn , het aantal *rijtjes van lengte n. [Merk op dat de rij (tn )∞ n=1 bijna de rij van Fibonacci is, ‘bijna’ omdat de start anders is.] Vanwege de bovenstaande recursie kunnen we tn schrijven als tn = αxn1 + βxn2 ,
n = 1, 2, 3, . . . ,
voor zekere constanten α en β, waarbij x1 en x2 de wortels zijn van de vierkantsvergelijking x2 = x + 1. Ga dit zelf na door de voorgestelde vorm in te vullen in de recursie. Dit geeft √ 1 x1 = (1 − 5); 2
en
√ 1 x2 = (1 + 5). 2
Omdat we weten dat t1 = 2 en t2 = 3 kunnen we tenslotte de constanten α en β berekenen uit het stelsel vergelijkingen √ √ √ √ α(1 − 5) + β(1 + 5) = 4 en α(1 − 5)2 + β(1 + 5)2 = 12. √ √ [doe dit zelf]. We vinden α = (5 − 3 5)/10 en β = (5 + 3 5)/10. Samenvattend kunnen we concluderen à √ à √ !n √ à √ !n ! 1 5−3 5 1− 5 5+3 5 1+ 5 IP {*rijtje van lengte n} = n + = 2 10 2 10 2 ³ √ √ n √ √ n´ 1 (5 − 3 5)(1 − 5) + (5 + 3 5)(1 + 5) . 10 · 22n
22. Uiteraard is Ω = {(x1 , . .Ã. , x6 )!: x1 < x2 < · · · < x6 ; xi ∈ {1, . . . , 49}}, en hierop kiezen we het 49 homogene model, #Ω = . Laat nu A de eventualiteit zijn dat niet twee opvolgende getallen 6 getrokken worden. Dus A = {(x1 , . . . , x6 ) ∈ Ω : ∀i ≥ 2 : xi − xi−1 ≥ 2}. Introduceer vervolgens de verzameing B van alle rijtjes getallen van lengte 6 uit de verzameling {1, 2, . . . , 44}. Dus B = {(x1 , . . . , x6 ) : x1 < x2 < · · · < x6 ; xi ∈ {1, . . . , 44}}.
19
We tonen vervolgens aan dat de verzamelingen A en B gelijkmachtig zijn. Definieer de functie f : B −→ A als volgt f (x1 , x2 , x3 , x4 , x5 , x6 ) = (x1 , x2 + 1, x3 + 2, x4 + 3, x5 + 4, x6 + 5). Het is niet moeilijk in te zien dat f een bijectie is [ga na!]. We krijgen nu Ã
IP {A} =
!
44 6
#A 22919 ! = =Ã ≈ 0.50480155. #Ω 45402 49 6
De conclusie is dat de kans dat bij de Lotto minstens twee opvolgende getallen getrokken worden ongeveer gelijk is aan 0.49519845, dus bijna 0.5. Dit is op het eerste gezicht zeer verrassend, omdat de gemiddelde ‘afstand’ tussen twee opvolgende getallen ongeveer 6 bedraagt [denk aan een ketting van 49 kralen waaruit je blindelings 6 kralen verwijdert; de 7 stukken hebben een gemiddelde lengte van ruim 6 kralen]. Voor de aardigheid berekenen we de verwachting van het kleinste getrokken getal, zeg X1 . Dus X1 (ω) = x1 voor ω = (x1 , . . . , x6 ). De waardenverzameling van X is WX = {1, . . . , 44}. Kies i ∈ WX . Dan krijgen we Ã
IP {X1 = i} =
1 1
!Ã Ã
49 − i 5
49 6
!
!
.
Ga dit na! Dan krijgen we IE[X1 ] =
44 X
iIP {X = i} = Ã
i=1
1 49 6
!
44 X
Ã
i
i=1
49 − i 5
!
=
50 , 7
dus ligt inderdaad ‘gemiddeld’ het kleinste getal in de buurt van de 7. Nu we toch bezig zijn, berekenen we ook nog even de verwachte ‘afstand’ tussen het kleinste getrokken getal X1 en het op ´e´en na kleinste getrokken getal, zeg X2 , dus X2 (ω) = x2 voor ω = (x1 , . . . , x6 ). De waardenverzameling van de stochastische vector (X1 , X2 ) is W = {(i, j) : 1 ≤ i < j ≤ 45}. Kies (i, j) ∈ W . Dan krijgen we à !à !à ! 1 1 49 − j 1 1 4 à ! IP {X1 = i; X2 = j} = . 49 6 Dit geeft voor de verwachte ‘afstand’ tussen het kleinste en het op ´e´en na kleinste getal IE[X2 − X1 ] =
44 X 45 X
(j − i)IP {X1 = i; X2 = j} = Ã
i=1 j=i+1
1 49 6
!
44 X 45 X
Ã
(j − i)
i=1 j=i+1
49 − j 4
!
=
50 . 7
Zoals te verwachten was, opnieuw ruim 7, zelfs exact gelijk aan IE[X1 ], wat natuurlijk niet verrassend is. 23. We kiezen het homogene model bij de uitkomstenruimte Ω = {1, 2, . . . , N }n . We fixeren ons nu eerst op een specifieke collectie van m verschillende nummers, zeg A ⊂ {1, . . . , N }. We berekenen vervolgens de kans, zeg p(A), dat alleen nummers uit de collectie A voorkomen, maar wel elk P nummer uit A minstens ´e´en keer. De gevraagde kans zal dan zijn A ⊂ {1,2,...,N }: #A=m p(A) = Ã
N m
!
p({1, . . . , m}), waarmee het probleem gereduceerd is tot het berekenen van de kans dat
20
alleen de nummers van 1 tot en met m voorkomen, en wel elk minstens ´e´en keer. Definieer de volgende deelverzamelingen van Rm := {1, . . . , m}n , Ej = {(x1 , . . . , xn ) ∈ Rm | ∀i : xi 6= j}. In het onderstaande is Ej∗ := Rm \Ej , dus Ej∗ is hier het complement van Ej met betrekking tot de gereduceerde verzameling Rm ⊂ Ω. Dan geldt met deze notatie en De Morgan
p({1, . . . , m}) = IP
m \
Ej∗ = IP
j=1
Ã
1 Nn
mn −
"m X
m [
∗
Ej =
#
h³S m
j=1 Ej
Nn
j=1
Ã
!
m k
(−1)k−1
k=1
#!
(m − k)n
´∗ i
m [ 1 = n #Rm − # Ej = N j=1
"
m 1 X (−1)k = n N k=0
Ã
m k
!
#
(m − k)n .
De voorlaatste formule volgt uit de algemene somregel voor aantallen [vergelijk met de somregel voor kansen!]
#
m [
Ej =
j=1
m X
X
(−1)k−1
# [Ei1 ∩ · · · ∩ Eik ] =
i1
k=1
m X
Ã
(−1)k−1
k=1
m k
!
(m − k)n .
Alles samenvattend kunnen we concluderen dat de kans dat precies m verschillende nummers getrokken worden gelijk is aan Ã
N m
!
"
m 1 X (−1)k N n k=0
Ã
m k
!
# n
(m − k)
.
We passen dit resultaat voor de aardigheid toe op de volgende vraag: wat is de kans dat 10 blindelings getrokken personen op slechts 5 verschillende dagen jarig zijn? Het antwoord is Ã
365 5
!
"
5 X 1 (−1)k 36510 k=0
Ã
5 k
!
# 10
(5 − k)
=
29371633114824 ≈ 6.38605013 · 10−9 . 4599342711583430703125
24. We lossen dit probleem op met de Wet van de totale waarschijnlijkheid [WTW]. Laat Sm de eventualiteit zijn dat Elisa de beste partner kiest via de m-strategie en Bi de eventualiteit dat de beste partner de partner is van de i-de ‘date’. Dan met de WTW, IP {Sm } =
n X
IP {Sm |Bi }IP {Bi },
i=1
omdat {B1 , . . . , Bn } een partitie van de uitkomstenruimte is. Onmiddeliijk zien we IP {Bi } = 1/n. Het probleem is nu gereduceerd tot het berekenen van de voorwaardelijke kansen IP {Sm |Bi }. Allereerst merken we op dat voor i ≤ m uiteraard geldt IP {Sm |Bi } = 0 [als de beste partner zich onder de eerste m ‘dates’ bevindt dan wordt hij zeker niet gekozen via de m-strategie]. Vervolgens kijken we naar i = m + 1. Dan zien we onmiddellijk IP {Sm |Bm+1 } = 1. Tenslotte voor i > m + 1, IP {Sm |Bi } =
m m+1 i−2 m · ··· = . m+1 m+2 i−1 i−1
Toelichting: bij de (m + 1)-ste ‘date’ is de kans m/(m + 1) dat deze niet beter is dan de beste van de eerste m ‘dates’; bij de (m + 2)-de ‘date’ is de kans dat deze niet beter is dan de beste van de eerste m, gegeven dat de (m + 1)-ste niet beter was dan de eerste m gelijk aan (m + 1)/(m + 2), etc. [ga dit na!]. Je kunt dit ook wat directer inzien: de kans dat je de beste partner kiest, gegeven dat de beste partner bij de i-de ‘date’ aangetroffen wordt is gelijk aan de kans dat onder de eerste i − 1 ‘dates’ de beste bij de eerste m zit, en deze kans is m/(i − 1). Alles samenvattend vinden we IP {Sm } =
n X
n m 1 m X 1 · = . i−1 n n i=m+1 i − 1 i=m+1
21
Vervolgens zien we uit een plaatje [teken!] dat log n =
Z n 1 1
u
Met deze benadering vinden we
du ≈
n X i=2
µ
IP {Sm } ≈
1 . i−1 ¶
n m log . n m
Laten we nu de eis dat m ∈ IN geldt los, dan krijgen we de volgende calculus-opgave: Bepaal het maximum van de functie µ ¶ x n h(x) := log . n x Differenti¨eren en afgeleide nul stellen geeft µ ¶
1 n h (x) = log n x 0
−
1 = 0. n
dus we vinden een maximum bij x = n/e, en de bijbehorende grootste succeskans is h(n/e) = 1/e.
5
Oefenopgaven 1. Vincent trekt achter elkaar kaarten uit een pak van 52 standaardkaarten. (a) Bereken de kans dat de eerste aas de dertiende kaart is. (b) Bereken de kans dat onder de eerste 13 kaarten precies ´e´en aas zit. 2. Bouke trekt uit een vaas waarin N genummerde ballen zitten 4 ballen zonder teruglegging. (a) Bereken de kans dat het kleinste getrokken nummer i is (i = 1, 2, . . . , N − 3). (b) Bereken de kans dat het grootste getrokken nummer j is (j = 4, 5, . . . , N ). (c) Bereken de kans dat het kleinste getrokken nummer i is en het grootste getrokken nummer j. 3. Chris gooit ´e´en keer met 4 zuivere dobbelstenen. (a) Bereken de kans dat het kleinste aantal ogen op een van de stenen i is. (b) Bereken de kans dat het grootste aantal ogen op een van de stenen j is. (c) Bereken de kans dat het kleinste aantal ogen op een van de stenen i is en het grootste aantal ogen op een van de stenen j.
22
