From Delft

Je kan op een eenvoudige manier de lootjes voor het maken van Sinterklaassurprises blind verdelen. Natuurlijk moet niemand voorzichzelf een surprise gaan maken, en de verdeling moet in één keer goed zijn. Bovendien mag niemand weten wie wie getrokken heeft. Natuurlijk moeten er meer dan twee mensen meedoen.

Je begint met enveloppen en kaartjes, met daarop de namen van de deelnemers. Na een aantal stappen zit in elke envelop een kaartje. Je weet niet welke envelop welk kaartje bevat, maar wel dat geen enkele envelop een kaartje met dezelfde naam heeft.

De methode hiervoor noem ik M1; deze staat verderop beschreven. Het is misschien leuk om zelf eerst een oplossing te bedenken.

Het zou kunnen dat er extra eisen zijn aan de verdeling van de kaartjes. Bijvoorbeeld er is een getrouwd stel, zeg A en B. Dan wil je niet dat A een surprise moet maken voor B, en omgekeerd. De eerste methode M1 kan eenvoudig worden aangepast om aan deze extra eis te voldoen. Dat lukt ook als er meerdere stellen zijn, waarvan de partners elkaar niet moeten trekken. Zo krijg je methoden M2 en M3.

Op Internet is een aantal sites waar je ook de lootjes kan laten verdelen; de deelnemers krijgen dan een email. Sommige sites bieden de mogelijkheid om allerlei trekkingen uit te sluiten. Dat is bijvoorbeeld handig als je wil dat niemand dezelfde persoon trekt die hij vorig jaar ook had. Maar ook dit soort eisen zijn mogelijk in een methode met enveloppen en kaartjes, dus zonder computer en email. Deze methode M4 is wel wat gecompliceerder dan de vorige.

Ik vond een beschrijving van het probleem in de eenvoudigste vorm in het tijdschrift Pythagoras.

… wat gebeurt er als iemand zichzelf trekt? Dan moet de trekking opnieuw. De kans dat zoiets gebeurt is vrij groot Dit overkwam de familie Lootsma vorig jaar. Tot drie keer toe moest er opnieuw getrokken worden. Op het laatst werden er lootjes herkend aan de manier waarop ze gevouwen waren. Zoiets wil je eigenlijk voorkomen.

Zou er geen oplossing te bedenken zijn voor dit probleem? Is het mogelijk om de trekking zo te organiseren dat niemand zichzelf trekt? Deze vraag stelde Alexander Rinnooy Kan, lid van de Raad van Bestuur van de ING-Bank, zich. Menig ledig kwartiertje besteedde hij aan deze puzzel. Toen hij vorig jaar in Eclaire, een tijdschrift voor economen, een artikel van Fransje Akveld over het trekken van lootjes zag staan, legde hij de schrijfster per brief het volgende probleem voor.

Kun je een manier bedenken om het lootjes trekken zo te organiseren dat niemand zichzelf trekt? Een correcte oplossing moet aan de volgende drie eisen voldoen:

• Hulp van buitenstaanders is niet toegestaan.
• Geen van de deelnemers mag aan het eind van de trekking informatie verkregen hebben over de uitslag.
• De trekking moet voldoende snel zijn. Steeds opnieuw trekken is daarom niet toegestaan, want dat kan in principe eindeloos duren.

Jan Brinkhuis heeft twee verschillende oplossingen van dit probleem bedacht. Zijn oplossingen kun je hieronder vinden. Bij oplossingen van dit soort problemen kun je je altijd afvragen of ze de best mogelijke oplossingen zijn. Wie heeft een beter idee?

De oplossingen van Jan Brinkhuis zijn vrij ingewikkeld, en daarom in de praktijk niet handig. De methodes die ik geef zijn wel eenvoudig toe te passen. 

Oplossingen

M1: Niemand mag zichzelf toegewezen krijgen 

• Doe alle kaartjes in de enveloppen waarop dezelfde naam staat; zorg ervoor dat de naam op de kaart aan dezelfde kant zit als de naam op de envelop.
• Leg de enveloppen op een stapel, met de namen naar beneden
• Schud de enveloppen zonder de namen te zien
• Er is nu een stapel enveloppen in willekeurige volgorde, met de namen naar benenden
• Schuif nu alle kaartjes 1 envelop door, zonder de namen te zien:
  – haal het kaartje uit de bovenste envelop, en leg dit apart
  – werk nu de enveloppen stuk voor stuk naar beneden af:
      stop er steeds het kaartje in dat je uit de volgende envelop haalt
  – stop het apart gelegde kaartje in de onderste envelop

• Schud de enveloppen zonder de namen te zien

M2: Nu mogen ook de twee partners van een stel elkaar niet toegewezen krijgen

• Doe alle kaartjes in de enveloppen waarop dezelfde naam staat; zorg ervoor dat de naam op de kaart aan dezelfde kant zit als de naam op de envelop.
• Houd de enveloppen apart voor het getrouwde stel met partners A en B
• Leg de overige enveloppen op een stapel, met de namen naar beneden
• Schud deze enveloppen zonder de namen te zien
• Verdeel deze enveloppen in 2 stapeltjes van (bijna) gelijke grootte
• Leg de envelop van A met de naam naar beneden op het eerste stapeltje, en die van B op het tweede
• Voor beide stapels: schuif alle kaartjes 1 envelop door
• Leg de stapels op elkaar zodat er 1 stapel overblijft
• Schud de enveloppen zonder de namen te zien

M3: Er zijn meer stellen waarvan de partners elkaar niet toegewezen mogen krijgen

• Doe alle kaartjes in de enveloppen waarop dezelfde naam staat; zorg ervoor dat de naam op de kaart aan dezelfde kant zit als de naam op de envelop.
• Houd de enveloppen voor alle getrouwde stellen paarsgewijs apart, in stapeltjes van 2 met de namen naar beneden
• Voor elk van die stapeltjes: schud het stapeltje zolang dat je niet meer weet welke naam op de bovenste kaart ligt
• Leg nu alle bovenste kaarten van de stapeltjes op een nieuwe stapel A, en de onderste op een nieuwe stapel B
• Leg de overige enveloppen op een stapel, met de namen naar beneden
• Schud deze enveloppen zonder de namen te zien
• Verdeel deze enveloppen zo gelijk mogelijk over stapels A en B, zonder de namen te zien
• Schud stapels A en B
• Voor beide stapels: schuif alle kaartjes 1 envelop door
• Leg de stapels op elkaar zodat er 1 stapel overblijft
• Schud de enveloppen zonder de namen te zien

M4: Er zijn willekeurige toewijzingen uitgesloten

Hiervoor zijn 2 verdelers nodig.

• De eerste verdeler schrijft de regels van verboden toewijzingen: Bijvoorbeeld A mag niet A, B of C toegewezen krijgen etc
• Dan schudt hij de enveloppen, en vervolgens de kaartjes
• Vervolgens schrijft hij de regels nogmaals op, op een nieuw vel papier, maar door de namen door volgnummers te vervangen:
• stel dat envelop A op de zevende plaats van boven ligt, en kaartjes A, B, C op de derde, achtste en bovenste plaats, dan zou hij in plaats van  “A mag niet A, B of C krijgen” opschrijven: ” 7 mag niet 3, 8 of 1 krijgen”
• Dan geeft hij het papier en de twee stapels (enveloppen en kaartjes) met de namen naar beneden, aan de tweede verdeler.
• Die bekijkt de regels op het papier, en schrijft een toegelaten verdeling op, in termen van de volgnummers: 1 krijgt 4 etc
• Vervolgens doet hij de kaartjes overeenkomstig in de enveloppen, zonder de namen te bekijken
• Tenslotte schudt hij de enveloppen zonder de namen te zien

Tot slot

Na afloop weet niemand wie wie getrokken heeft. Maar je kan beargumenteren dat er niet is voldaan aan de tweede eis die Rinnooy Kan stelde: Geen van de deelnemers mag aan het eind van de trekking informatie verkregen hebben over de uitslag. Stel namelijk dat methode M1 wordt gebruikt. De verdeler heeft dan toch wat informatie over de uitslag. De trekking is namelijk eigenlijk 1 grote lus, van het type: A krijgt B; B krijgt C; … Z krijgt A. Kleinere lussen zoals A krijgt B en B krijgt A zijn niet mogelijk. Dit is extra informatie, maar niet genoeg om ook maar 1 toewijzing te weten.

Methode M1 sluit op deze manier vrij veel toewijzingen uit.

De kleinste lussen zijn van het type “A krijgt A”. In het Pythagoras artikel staat dat het aandeel van de denkbare trekkingen geen lus van dat type bevat, ongeveer gelijk is aan 1/e. Hier is e het getal van Euler, ongeveer 2,7183. 1/e is ongeveer 37%. Dat percentage de denkbare trekkingen blijft over, als we alleen de kleinste lussen uitsluiten.

Methode M1 laat veel minder over van de denkbare trekkingen. Stel er zijn n deelnemers. Dan is het aantal mogelijke volgorden van enveloppen na het schudden gelijk aan 1*2*…*(n-1)*n = n! (“n faculteit”). Dit is ook het aantal denkbare trekkingen. Iedere mogelijke volgorde van de enveloppen maakt weer een andere lus, maar steeds zijn groepen van n lussen toch weer gelijk: zo’n lus bestaat uit n punten, als je die een aantal punten roteert heb je effectief dezelfde toewijzing, bijvoorbeeld B krijgt C; … Z krijgt A; A krijgt B. Het aantal effectief verschillende lussen is daarom n maal zo klein: 1*2*…*(n-1) = (n-1)!.

In plaats van 37% blijft nog maar 1/n van de denkbare toewijzingen over met methode M1. 

Methode M1 was in 2007 gepost op een puzzelsite.

This entry was posted on November 20, 2008 at 2:06 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.