1: Twee Sinterklaasproblemen
2: Oplossing probleem 1
3: Eerste oplossing probleem 2
4: Tweede oplossing probleem 2
In honderdduizenden gezinnen, families, schoolklassen en sportclubs worden elk jaar lootjes getrokken voor de viering van Sinterklaas. Dat kan verschillende problemen geven: lootjes kunnen zoek raken of iemand kan zichzelf trekken. Hoe kun je er voor zorgen dat het lootjes trekken vlekkeloos verloopt?
Lootjes trekken voor Sinterklaas geeft elk jaar weer problemen. Ook dit jaar was dat het geval bij de familie Lootsma. Hun oudste zoon Pieter is wiskunde gaan studeren en kon wegens zijn tentamens de weken voor Sinterklaas niet thuiskomen. Hoe konden er nu lootjes getrokken worden? Mevrouw Lootsma belde haar oudste zoon op en vroeg hem om zijn verlanglijstje. Vervolgens riep ze de rest van het gezin bij elkaar. Iedereen deed zijn eigen verlanglijstje in een envelop en mevrouw Lootsma deed hetzelfde met Pieter's lijstje. Alle enveloppen, behalve die met Pieter's verlanglijstje werden op tafel gelegd en door elkaar geschud. Toen niemand meer wist welke envelop welk lijstje bevatte, pakte moeder er een envelop uit: die was voor Pieter. Omdat zijn lijstje apart gehouden werd, kon Pieter zichzelf niet getrokken hebben en kon de envelop met verlanglijstje met een gerust hart opgestuurd worden. Daarna werd de envelop met Pieters verlanglijstje bij de andere enveloppen gevoegd en werden de enveloppen weer flink door elkaar gehusseld. Vervolgens trok de rest van de familie een envelopen gelukkig trok niemand zichzelf.
Mevrouw Lootsma was zeer tevreden. Ze kon die ene envelop naar Pieter sturen en iedereen kon beginnen aan de surprises.
In haar enthousiasme stuurde mevrouw Lootsma de envelop naar het verkeerde adres. Omdat sommige familieleden al cadeautjes gekocht hadden, kon er niet opnieuw getrokken worden. Wat te doen?
Weliswaar wist mevrouw Lootsma waar ze de envelop heen gestuurd had, maar die mensen waren voor een lange tijd op vakantie.
Probleem nr. 1 Hoe kan mevrouw Lootsma er voor zorgen dat Pieter te weten komt wie hij heeft getrokken en wat het verlanglijstje van diegene is? De oplossing moet tot stand komen zonder hulp van buitenstaanders. Bovendien moet de verdeling van de lootjes geheim blijven; niemand mag door de oplossing extra informatie krijgen over wie wie heeft getrokken.
Zelfs als iedereen aanwezig is bij de trekking van de lootjes kan er van alles mis gaan. Want wat gebeurt er als iemand zichzelf trekt? Dan moet de trekking opnieuw.
De kans dat zoiets gebeurt is vrij groot (zie inzet). 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.
Probleem nr. 2 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 kans dat je jezelf trekt.
De kans dat tijdens het lootjes trekken iemand zichzelf trekt kun je berekenen door de mogelijkheden na te gaan. Met twee personen is het aantal mogelijkheden beperkt. Nummer 1 trekt 1 en nummer 2 trekt 2, of 1 trekt 2 en 2 trekt 1. Deze mogelijkheden kun je weergeven met: 1,2 en 2, 1. De kans dat iemand zichzelf trekt is dus 1/2. Bij drie personen zijn er zes mogelijkheden: 1,2,3; 2,1,3; 3,1,2; 1,3,2; 2,3,1; 3,2,1. Vetgedrukt zijn de nummers die zichzelf getrokken hebben. De kans dat niemand zichzelf trekt is dus 2/6. Bij 4 personen zijn er 24 mogelijkheden, bij vijf al 120. In het algemeen zijn er voor n personen n! mogelijkheden en
de kans dat niemand zichzelf trekt is gelijk aan:
Als je n laat toenemen dan verandert vanaf n=6 de kans bijna niet meer.
Dat is toch verrassend!
De kans dat een trekking in één keer goed gaat hangt dan
nauwelijks van de groepsgrootte af en is praktisch gelijk aan 1/e=0.36677...
1 | 2 | 3 | 4 | next
|
