Bericht
door arie » 21 mei 2008, 19:59
Als we 5 personen A B C D en E hebben, dan zijn er 5! = 120 mogelijke trekkingen.
Als persoon A als eerste trekt, zijn de uitkomsten:
1: Axxxx blijft over {B,C,D,E}
2: Bxxxx blijft over {A,C,D,E}
3: Cxxxx blijft over {A,B,D,E}
4: Dxxxx blijft over {A,B,C,E}
5: Exxxx blijft over {A,B,C,D}
dus voor A gaat het in 4/5 van de gevallen goed.
In deze gevallen is steeds 1 persoon toegekend aan A (in het 2e geval B, in het 3e geval C etc).
Nu wordt het probleem verkleind: we moeten alleen nog de kans berekenen dat 4 personen niet zichzelf
trekken uit lootjes waarvan 3 namen in die groep zitten en 1 iemand altijd iemand anders trekt:
namelijk degene die door A getrokken is.
Neem die persoon apart en kijk welke die trekt, bijv 3e geval: A trekt C, bekijk nu alles voor C:
Axxx blijft over {B,D,E}
Bxxx blijft over {A,D,E}
Dxxx blijft over {A,B,E}
Exxx blijft over {A,B,D}
in 1/4 van de gevallen trekt C lot A, dan moeten we kijken hoe groot de kans is dat uit de overige
3 niemand zichzelf trekt, waarbij de 3 namen van de personen op de lootjes staan.
in de andere 3 gevallen, met kans 3 * 1/4 = 3/4, zit A bij de rest, en moeten we de kans bereken dat
niemand van die 3 zichzelf trekt uit ( 2 van hun namen + een andere naam ).
Nu hebben we het gehele probleem verkleind:
noem P[n] de kans dat niemand uit n zichzelf trekt
noem Q[n] de kans dat niemand uit n zichzelf trekt uit (n-1) + 1 vreemde naam
Dan is:
P[n] = ((n-1)/n) * Q[n-1]
(zie de eerste trekking hierboven: P[5] = 4/5 * Q[4])
Q[n] = (1/n) * P[n-1] + ((n-1)/n) * Q[n-1]
(tweede trekking: Q[4] = 1/4 * P[3] + 3/4 * Q[3])
Als we nu nog kijken naar een trekking door 2 personen A en B, dan kunnen de uitkomsten zijn:
AB
BA
de kans dat niemand zichzelf trekt = P[2] = 0.5
Zijn er 2 personen die trekken uit 1 eigen naam en 1 vreemde naam, bv personen A en B
hebben lootjes A en F, dan zijn de trekkingen:
AF
FA
de kans dat hier niemand zichzelf trekt (A dus) is Q[2] = 0.5
Samenvattend hebben we:
P[n] = ((n-1)/n) * Q[n-1]
Q[n] = (1/n) * P[n-1] + ((n-1)/n) * Q[n-1]
met
P[2] = 0.5
Q[2] = 0.5
We kunnen nu voor elke n de gevraagde kans P[n] uitrekenen door eerst
P[3] en Q[3] te berekenen, daaruit P[4] en Q[4], etc.
Het aantal goede trekkingen uit de in totaal n! mogelijkheden is dan (n!)*P[n]:
n=3: (n!)*P[n]=2
n=4: (n!)*P[n]=9
n=5: (n!)*P[n]=44
n=6: (n!)*P[n]=265
n=7: (n!)*P[n]=1854
Je kan deze formule nog mooier maken door Q weg te werken:
P[n] = ((n-1)/n) * P[n-1] + (1/n) * P[n-2].
met
P[1] = 0 (de kans dat 1 persoon met 1 lot niet zichzelf trekt is nul)
P[2] = 0.5
Dit mag je verder zelf aantonen.
Vergelijk dit ook eens met de konijnen van Fibonacci:
K[n] = K[n-1] + K[n-2]
met
K[1]=K[2]=1.
Kom je er zo uit?
Laatst gewijzigd door
arie op 27 mei 2008, 15:48, 1 keer totaal gewijzigd.
)