De knappe koppen van 5 havo

Ik heb het geluk gehad altijd les te mogen geven aan knappe leerlingen. De leerlingen zijn niet alleen knap, maar hebben ook mooie namen. Dit zijn de 16 leerlingen in mijn 5 havo klas:
Ans, Bob, Cynthia, Daphne, Els, Fatima, Grace, Hanna, Ine, Josje, Kim, Lucas, Maria, Nico, Otto en Pia.

Deze leerlingen vinden het leuk intellectuele uitdagingen aan te gaan. Dit jaar daagde ik ze uit met het postvakjesprobleem:
CYN
Kaartje van Cynthia
Op de muur naast het lokaal zijn 16 postvakjes met de letter A t/m P erop, zodat elke leerling zijn eigen postvakje heeft.
Er zijn ooit mooie kaartjes gemaakt met de eerste drie letters van de namen van de leerlingen erop. Ik stopte in elk postvakje een van deze kaartjes, maar deed dat willekeurig. De opdracht voor de leerlingen is om hun eigen kaartje te vinden. Hiertoe mogen de leerlingen maximaal 8 postvakjes open maken. Ze doen dat na elkaar - in willekeurige volgorde - zonder te zien wat anderen hebben geopend en ze overleggen alleen vooraf (als ze dat nodig vinden). Als ze hun kaartje gevonden hebben, dan laten ze dat liggen. De opdracht is geslaagd als alle leerlingen na maximaal acht postvakjes openen hun kaartje vinden.
De eerste reactie van een van de leerlingen was: de kans dat dat lukt is toch (1/2)16 ≈ 0,000015?
Toevallig was op dat moment de onderwijsassistent Souffian aanwezig. Hij riep:
“Dat klopt als je willekeurig postvakjes opent, maar als je het slim doet dan wordt die kans groter dan 1/3.
Sterker nog, de kans is 100% als ik vooraf maximaal twee kaartjes omwissel.”

Hierop zei Grace: “Ik weet hoe het moet, zullen we overleggen?”
Niet nodig vonden de andere leerlingen. “Wij weten ook hoe het moet!”

Oplossing

Dit probleem is een variant op het bekende 100 gevangen probleem. De clou is dat je de postvakjes niet willekeurig opent, maar er een ketting van maakt.
Je begint met het openen van je eigen postvakje (dus stel dat je Pia bent, dan open je postvakje P). Je kijkt op het kaartje en opent nu het vakje van de persoon die op het kaartje staat. Dus als er Ans op staat dan open je vakje A. Je gaat door tot je je eigen naam vindt. Je onthoudt in welk postvakje dat is, maar laat je kaartje liggen. Als je meer dan 8 vakjes hebt opengemaakt dan stopt iedereen want er kan niet meer gewonnen worden.

Waarom werkt dit?

Als je op deze wijze werkt dan is een ding zeker: je eigen kaartje komt ergens in de ketting voor, maar misschien pas na het achtste postvakje. Het stukje van de ketting dat je gebruikt voordat je je eigen naam treft wordt met het Engelse woord cycle aangeduid. Elke leerling die je bent tegengekomen op de kaartjes zit in dezelfde cycle en kan nooit in andere cycle terechtkomen. In een reeks van 16 postvakjes kan een verschillend aantal cycles zitten, maar de totale lengte van alle cycles opgeteld is altijd 16. Het is duidelijk dat er in een ketting van 16 schakels, hooguit één cycle kan zitten die langer is dan 8. We moeten dus uitrekenen hoe vaak dat voorkomt bij een willekeurige volgorde van de 16 kaartjes in de postvakjes. Laten we als voorbeeld nemen een cycle met een lengte van 9. Misschien heb je bij wiskunde geleerd dat je dit op "16 boven 9" manieren kunt kiezen (rekenmachine 16 nCr 9). Dat kan op maar liefst 11440 manieren. Bij elk van deze verdelingen kun je de getallen willekeurig verwisselen, zowel in de cycle van 9 als in de overige 7 getallen. We moeten dus nog vermenigvuldigen met 8! (niet 9!, omdat een cyclische verschuiving niet uitmaakt) en met 7!.
Als je naar de definitie van "16 boven 9" kijkt dan zie je dat je een en ander kunt wegstrepen, zodat alleen de term 16!/9 overblijft. Omdat je een kans wilt hebben, moet je nog delen door het totaal aantal mogelijk volgordes (= 16!). Je houdt alleen 1/9 over. Om de totale kans te berekenen op een cycle die langer is dan 8 moet je hierbij de kansen op de andere lengtes groter dan 8 optellen. Om de kans te krijgen dat je GEEN cycle groter dan 8 hebt, moet je 1 minus nemen. De kans dat er geen langere cycle dan 8 is (dus de kans dat iedereen zijn kaartje op tijd vindt) is dus 1− (1/9+1/10+1/11+1/12+1/13+1/14 +1/15+1/16) ≈ 0,337. Het klopt dus wat Souffian zei.

Een paar interessante feitjes:

Een uitgewerkt voorbeeld met vier leerlingen

Het is heel lastig om de situatie met 16 leerlingen helemaal uit te werken. Met vier leerlingen en vier postvakjes lukt dat wel. Zou je willekeurig kiezen dan is de kans dat alle leerlingen binnen twee keer proberen hun eigen kaartje vinden (1/2)4 = 0,0625.
Met de slimme werkwijze wordt dat maar liefst 1 − 1/31/4 ≈ 0,4167. Hieronder zie je alle 16 manieren waarop de kaartjes over de vier postvakjes verdeeld kunnen zijn. De postvakjes zijn in de volgorde A B C D.

Ans  Bob  Cyn  Dap Bob  Ans  Cyn  Dap Cyn  Ans  Bob  Dap Dap  Ans  Bob  Cyn
Ans  Bob  Dap  Cyn Bob  Ans  Dap  Cyn Cyn  Bob  Ans  Dap Dap  Bob  Cyn  Ans
Ans  Cyn  Bob  Dap Bob  Cyn  Ans  Dap Cyn  Bob  Ans  Dap Dap  Bob  Ans  Cyn
Ans  Cyn  Dap  Bob Bob  Cyn  Dap  Ans Cyn  Bob  Dap  Ans Dap  Bob  Cyn  Ans
Ans  Dap  Bob  Cyn Bob  Dap  Ans  Cyn Cyn  Dap  Ans  Bob Dap  Cyn  Ans  Bob
Ans  Dap  Cyn  Bob Bob  Dap  Cyn  Ans Cyn  Dap  Bob  Ans Dap  Cyn  Bob  Ans


Het eerste vakje krijg je als toevallig alle kaartjes in de juiste postvakjes zijn terechtgekomen. Dan is iedereen na een keer in een postvakje kijken klaar. De blauw gekleurde vakjes geven de situaties waarin iedereen binnen twee maal proberen zijn kaartje vindt.
Als voorbeeld neem ik Cyn Dap Ans Bob:
Ans opent vakje A en vindt het kaartje van Cynthia
Ans opent vakje C en vindt het kaartje van Ans: klaar na twee postvakjes
Bob opent vakje B en vindt het kaartje van Daphne
Bob opent vakje D en vindt het kaartje van Bob: klaar na twee postvakjes
Cynthia opent vakje C en vindt het kaartje van Ans
Cynthia opent vakje A en vindt het kaartje van Cynthia: klaar na twee postvakjes
Daphne opent vakje D en vindt het kaartje van Bob
Daphne opent vakje B en vindt het kaartje van Daphne: klaar na twee postvakjes
De volgorde waarin de leerlingen naar de postvakjes toegaan maakt niet uit.
We kunnen de kans ook berekenen door te tellen: 10 van de 24 mogelijkheden zijn goed, dat is inderdaad 0,4167

Maar Souffian zei toch nog iets?

Soufian zei dat als hij vooraf twee kaartjes mag omwisselen, hij de kans op succes kan verhogen tot 100%. Hij moet dan wel de kaartjes kunnen bekijken. Hoe gaat hij te werk? Hij zoekt uit of er een cycle is die langer is dan de helft van het aantal postvakjes. Zo nee, dan doet hij niets. Zo ja, dan verwisselt hij twee kaartjes, zodanig dat de cycle verbroken wordt. Dat is altijd mogelijk.
Om de grootste cycle te vinden start hij met postvakje A en volgt de cycle. Als deze korter is dan 8, dan gaat hij naar het eerstvolgende vakje dat hij nog niet geopend heeft. Als hij dan al meer dan 8 vakjes in totaal heeft geopend weet hij dat er geen langere cycle te vinden is. Hij hoeft dus niet altijd alle postvakjes te bekijken.
Een voorbeeld: stel we hebben de volgende situatie:
ABCDEFGH IJKLMNOP
AnsCynDapElsJosBobHan FatGraIneKimLucMarNicOttPia
De bovenste rij zijn de letters op de postvakjes, de onderste rij de naam op het kaartje dat in het postvakje zit.
Souffian opent het eerste vakje en vindt het kaartje van Ans. De cycle is klaar. Dan gaat hij naar vakje B en opent daarna achtereenvolgens vakje C, D, E, J, I, G, H en F. Pas bij F vindt hij het gezochte kaartje van Bob. Deze cycle is te lang. Hij moet dus binnen deze cycle twee kaartje omwisselen zodat de cycle wordt gebroken. Er zijn verschillende mogelijkheden, maar niet elke omwisseling werkt, dus controleert Souffian dit nog even. Stel dat hij de kaartjes van Jos en Fatima omwisselt. Dan opent hij vanaf vakje B de postvakjes C, D, E en F. De volgende cycle begint bij postvakje G. Na G opent hij H, J en I. Er is geen langere cycle dan die vanaf vakje B. De leerlingen zullen altijd hun kaartje op tijd vinden.
Omdat Souffian altijd het laatste kaartje uit de cycle verwisselt met het middelste kaartje hoeft hij het niet te controleren.

Computerprogramma's

Hieronder zie je een Python 3 programma, waarmee je de kans voor een willekeurig grote groep kunt berekenen.
while True:
    n = int(input('Geef het aantal leerlingen op: '))
    if n % 2 != 0:
        print('Het aantal leerlingen moet een even getal zijn')
    else:
        break
    
def H(N): 
    som = 0
    for x in range(N//2 + 1, N + 1):
        som += 1/x
    return som

print('De kans dat de leerlingen "slagen" is ', 1 - H(n))

Een JavaScript simulatie

Geef hier op hoeveel leerlingen en dus postvakjes je hebt: