Het Sinterklaasprobleem

Het probleem van vandaag is niet dat van de kleur van de knechten van de Goedheiligman maar dat van het trekken van de lootjes. Wat is de kans dat dat in één keer goed gaat? Kun je het in één keer goed laten gaan?

De kans dat het goed gaat

Als je de namen van alle deelnemers op een papiertje schrijft en daarna iedereen een papiertje uit de hoed (o.i.d.) laat trekken wat is dan de kans dat niemand zichzelf trekt?
Om die kans te kunnen bepalen moet je twee dingen tellen: het totaal aantal manieren waarop de papiertjes uit de hoed getrokken kunnen worden èn het aantal gunstige mogelijkheden. Het laatste aantal gedeeld door het eerste geeft dan de gewenste kans.

Als je dit wiskundig aan wil pakken maak je de situatie zo eenvoudig mogelijk: zet de mensen op een rij, en nummer ze: 1, 2, …, n. Na de trekking zet je persoon i op de plaats van degene die haar getrokken heeft. Op die manier komt een trekking overeen met het op één of andere volgorde zetten van de getallen 1, 2, …, n. Een gunstige trekking is er één waarbij elk getal van zijn (natuurlijke) plaats gehaald wordt.

Je kunt voor kleine n de tellingen met de hand uitvoeren maar het wordt al gauw een beetje onoverzichtelijk: de gevallen n=1 en n=2 zijn een beetje triest, die slaan we maar over. Bij n=3 kunnen we zes trekkingen uitvoeren (schrijf de volgordes maar eens op) en daarvan zijn er twee gunstig: (2,3,1) en (3,1,2). De kans dat het goed gaat is dus 1/3.

Bij een groep van vier mensen zijn er 24 mogelijk trekkingen: de eerste kan vier papiertjes trekken, de tweede drie, de derde twee en de laatste één. Dat levert 4×3×2×1=24 mogelijke volgordes. Het aantal gunstige mogelijkheden is wat lastiger te tellen: je kunt 1 en 2 omwisselen en ook 3 en 4, of 1 en 3 en ook 2 en 4, of 1 en 4 en ook 2 en 3. Dat geeft drie mogelijkheden. Je kunt de getallen ook doorschuiven: zet de mensen in een kring en laat iedereen een positie (naar links) opschuiven; we zetten 1 telkens op dezelfde vaste plek en zetten de andere drie willekeurig neer en dat levert nog zes mogelijkheden. In totaal 9 gunstige rangschikkingen met kans 9/24, ofwel 3/8.

Wie wil puzzelen kan proberen het aantal gunstige rangschikkingen uit de in totaal 5×4×3×2×1=120 manieren om vijf mensen te plaatsen te tellen maar dat wordt al behoorlijk bewerkelijk.

Inclusie-Exclusie

Er is een manier om de telling van het aantal gunstige manieren systematisch te tellen en die manier is ook op veel andere problemen toepasbaar. Het blijkt makkelijker het aantal ongewenste trekkingen te tellen.

Neem een getal n en bekijk de verzameling {1,2,…,n}. Die verzameling kan op n×(n-1)×…×1 manieren gerangschikt worden (het argument hierboven voor n=4 blijft van toepassing). Dat getal noteren we met n! (spreek uit: n-faculteit).
Voor iedere i noteren we de verzameling rangschikkingen die i op haar plaats laten met D_i. We willen dus tellen hoeveel elementen er in de vereniging D₁∪D₂∪…∪D_n zitten.
Voor het gemak voeren we nog de notatie |X| voor het aantal elementen van de verzameling X in.

Teken een plaatje met twee verzamelingen, zeg X en Y, en ga na dat we |X∪Y| als volgt uit kunnen drukken:
|X∪Y|=|X|+|Y|-|X∩Y|
immers: in de som |X|+|Y| tellen we de punten in X∩Y dubbel en daarom moeten we |X∩Y| aftrekken.

Teken een plaatje met drie verzamelingen, X, Y en Z, (met alle mogelijke doorsneden er in) en ga na dat
|X∪Y∪Y∪Z|=|X|+|Y|+|Z|-(|X∩Y|+|X∩Z|+|Y∩Z|)+|X∩Y∩Z|
immers: in |X|+|Y|+|Z| tellen we |X∩Y|+|X∩Z|+|Y∩Z| dubbel, dus dat trekken we af; maar nu zijn de punten in X∩Y∩Z drie keer meegeteld en drie keer afgetrokken, daarom tellen we |X∩Y∩Z| weer op

Als we dit toepassen op het geval n=3 dan krijgen we
|D₁|+|D₂|+|D₃|-(|D₁∩D₂|+|D₁∩D₃|+|D₂∩D₃|)+|D₁∩D₂∩D₃|
als het aantal ongewenste rangschikkingen; omdat |D_i|=2 voor elke i, en omdat |D_i∩D_j|=1 als i≠j en omdat |D₁∩D₂∩D₃|=1 vinden we 2+2+2-(1+1+1)+1=4 rangschikkingen waarbij ten minste één punt op zijn plaats blijft. We krijgen dus ons eerder gevonden aantal goede rangschikkingen terug.

In het algemene geval gebeurt hetzelfde: eerst de individuele aantallen optellen, dan twee-bij-twee doorsneden aftrekken, drie-bij-drie doorsneden optellen, vier-bij-vier aftrekken …. Dit heet het Principe van Inclusie-Exclusie.

Er zit veel regelmaat in onze aantallen:

• |D_i|=(n-1)! (de andere punten mogen willekeurig gerangschikt worden
• |D_i∩D_j|=(n-2)! (de andere punten mogen willekeurig gerangschikt worden
• elke k-bij-k doorsnede heeft (n-k)! elementen

Het aantal k-bij-k doorsneden is gelijk aan n!/(k!×(n-k)!) en dat maakt onze berekening heel overzichtelijk: er zijn

slechte rangschikkingen en dus

goede rangschikkingen. Als we dat aantal door n! delen komen we uit op een succeskans van

bij het lootjes trekken met n personen.
Omdat de termen in de som in absolute waarde steeds kleiner worden en beurtelings positief en negatief zijn volgt dat die kans altijd tussen 1/3 en 3/8 zal liggen.

Altijd succes?

Voor wie wil weten hoe je in één keer een goede trekking kunt verrichten: lees deze column van de Wiskundemeisjes uit 2009.
De methode komt er op neer dat je de deelnemers in een kring zet en hun naambriefjes aan de persoon links laat geven (met een truc om het geheim te houden natuurlijk).

Voor wie van puzzelen houdt: vlooi maar eens uit dat de kans dat er bij willekeurig trekken een permutatie als in die column uit komt gelijk is aan 1/n.

Be Sociable, Share!

• 
•