Wiskundemeisjes

Ionica & Jeanine
 
Slik Internetbureau Rotterdam Internetbureau Rotterdam



Categorieën

Archief

Lootjes trekken


In Column, door Jeanine

Deze column verscheen in de Volkskrant van 7 november.

Over vier weken is het zover: pakjesavond! Dat betekent dat er lootjes getrokken moeten worden. Ik woon een heel eind bij mijn ouders vandaan; het is al moeilijk om iedereen bij elkaar te krijgen op pakjesavond, maar het lukt ons maar zelden om ook nog eens bij elkaar te komen om lootjes te trekken.

Nou zijn er voor de hand liggende oplossingen als lootjes trekken op internet, maar de romantiek is er dan toch een beetje af. Zo’n lootje hoort een snippertje papier te zijn dat een maand lang rondzwerft in je broekzak of portemonnee, en niet een e-mail in je inbox.

sint

Mijn moeder stuurt dit jaar de lootjes met de post rond. Ze slaagt erin om iedereen een lootje te sturen waar zeker niet zijn eigen naam op staat, ze weet buiten zichzelf van niemand wie hij heeft, en er is geen hulp van buitenaf nodig. Hoe doet ze dat?

We willen met z’n zessen sinterklaas vieren. Mijn moeder neemt zes identieke enveloppen en schrijft op de voorkant van elke envelop één naam. Daarna schrijft ze elke naam ook op een velletje papier. Ze stopt elk briefje (opgevouwen) in de envelop waar dezelfde naam op staat als op het briefje, maar ze plakt de enveloppen natuurlijk nog niet dicht.

Ze legt alle enveloppen op de kop op een stapeltje, zodat ze de namen niet meer kan zien, en ze schudt het stapeltje goed. Vervolgens legt ze de enveloppen (nog steeds op de kop) in een cirkel op tafel. Ze haalt de velletjes uit de enveloppen (zonder te kijken wie erop staat!) en ze schuift alle velletjes één envelop door. Dan stopt ze elk velletje in de envelop waar het nu bij ligt, ze plakt de enveloppen dicht, ze husselt ze nog even door elkaar, en klaar! Nu heeft zeker niemand zichzelf, en mijn moeder weet van niemand anders wie hij heeft.

Ze had de papiertjes in plaats van één envelop ook twee, drie, vier of vijf enveloppen kunnen doorschuiven. Gaat het dan nog steeds goed? Onthoud dat mijn moeder wéét hoeveel ze alles doorgeschoven heeft.

Stel dat de enveloppen in de cirkel in de volgorde A, B, C, D, E, F lagen en ze schuift alle briefjes één envelop naar rechts. Dan ontstaat er een kringetje van lengte zes (F heeft E, E heeft D, enzovoorts). Ook als ze alles vijf enveloppen doorschuift, ontstaat er een kring van zes. Als ze alles twee of vier enveloppen doorschuift, ontstaan er twee kringetjes van lengte drie. Als alles drie enveloppen doorgeschoven wordt, dan worden alle kringetjes twee lang: A en D hebben elkaar, B en E ook, en C en F ook.

Kortom: mijn moeder weet wat voor kringetjes er ontstaan. En als ze alles drie enveloppen opschuift, weet ze dus dat de persoon die zij getrokken heeft ook háár lootje getrokken heeft! Dat mag niet.

En voor andere families? Met hoeveel personen je ook bent (mits meer dan drie): alle briefjes één envelop doorschuiven werkt altijd. Een aanrader voor alle families met ver weg wonende kinderen!

33 reacties op “Lootjes trekken”

  1. Relinde:

    Geweldig! Zo doen wij dat thuis ook al jaren! Met dank aan het Gotcha-spel met het wiskundedispuut in Leiden, in mijn eerste jaar :-) Bijkomend voordeel van deze methode is dat je het adres erbij kan zetten op de envelop, postzegel erop, en het lootje komt via de ouderwetse post naar je toe.

  2. Hugo:

    Wacht even hoor, ook bij 1x doorschuiven heeft moeder extra informatie. Met name weet ze zeker wie haar niet getrokken heeft (dat is degene die ze zelf heeft).

    Volgens mij moet er (voor het mooie) dus een perforator aan te pas komen. Briefjes in de eigen enveloppen, gaatje door-en-door in iedere envelop. Dan briefjes eruit en willekeurig er weer in, net zolang tot er geen enkel gaatje zichtbaar is. Toch?

  3. Jeanine:

    @ Hugo: nou ja, als iedereen weet dat moeder het eerlijk doet (en dus niet drie enveloppen doorschuift, maar bv een of twee) weet iedereen zeker dat degene die hij heeft hem niet ook heeft, natuurlijk. Maar dat vind ik niet erg. Het is alleen niet leuk als iemand van iemand anders zeker weet wie hij heeft.

  4. Sponzen Ridder:

    @Hugo: kan ze niet eerst aan de vader vragen om de briefjes eerst een onbekende afstand door te schuiven? En er dan zelf enkele bij doen. Als ze zichzelf heeft getrokken, weet ze dat ze opnieuw moet beginnen.

    Maar wat als je met koppels zit die ook voor elkaar geen kadootjes willen kopen? Is er dan ook een eenvoudige oplossing?

  5. Johan:

    Sponzen ridder heeft een goede oplossing. Briefjes gedekt leggen en iemand anders laten schuiven en zelf schuiven. (Herhalen als je jezelf hebt) lost alle problemen op.

  6. Rogier:

    En als je een willekeurige trekking doet met N personen, wat is de kans dat niemand zichzelf trekt, als N naar oneindig gaat?

    Dat gaat naar 1/e.

  7. Philip:

    Johan en sponzen ridder: in dat geval moet je toch met zn tweeën zijn. Het ging erom hoe je het doet in als je in je eentje werkt.

  8. Johan:

    @Philip: uiteraard, daar had ik even overgelezen.
    @Rogier: kan je een voorzet/oplossing geven om die kans te bepalen?

  9. Jan Paul:

    Wat een geweldige columns zijn dit toch!

  10. Relinde:

    @ Sponzen Ridder: voor koppels kom je er denk ik ook wel uit. Eerst hussel je de enveloppen van het koppel, en legt die ver uit elkaar. Vervolgens hussel je de rest, en je vormt een kring met het koppel niet direct na elkaar. De moeder weet dan wel hoeveel stappen er tussen het koppel zitten, maar als er genoeg mensen meedoen, dan geeft dit geen extra informatie. Hiervoor moet je denk ik wel minstens zes mensen hebben.

  11. Webraket:

    Nadeel van de oplossing van Sponzen Ridder lijkt me dat je dan misschien in de kringetjes terecht komt die Jeanine vermeldt. Toch ook niet zo leuk als iedereen iets terugkrijgt van degene aan wie hij/zij iets geeft.

  12. Jos:

    Het kan met koppels ook anders. Het is mogelijk om een willekeurig aantal koppels elkaar niet te laten trekken.
    Je deelt iedereen (ook degene die niet al een koppel zijn) op in paren (eventueel voeg je een dummy toe bij een oneven aantal mensen). Per paar neem je 1 envelop en stopt daar beide namen in (op gesloten lootjes). Dan hussel je de enveloppen, en daarna stop je uit elke envelop een lootje 1 verder in de cirkel en een lootje 2 verder in de cirkel. Vervolgens hussel je per envelop de 2 lootjes door elkaar en stuur het ene lootje naar de eerste van het koppel en het andere lootje naar de tweede van het koppel. De persoon die de dummy heeft getrokken belt op naar degene die de lootjes heeft verdeeld en krijgt dan de envelop van de dummy opgestuurd.

    De extra informatie die je krijgt is dat je partner niet de partner van jouw lootje heeft.

    De dummy kan overigens voor een fout zorgen als het aantal mensen kleiner is dan 9 (en oneven). Het is dan mogelijk dat degene die de dummy trok, getrokken werd door de dummy.
    Misschien dat het bij kleine aantallen nog te veel informatie geeft, daar heb ik nog niet over nagedacht.

  13. Johannes Verelst:

    Cool, ik ben in 2003 afgestudeerd met een scriptie met de illustere titel: "Secure computing and distributed solutions to the Secret Santa problem" :-).

    Voor de liefhebber: ik heb nog wel ergens een PDFje liggen. Het nadeel van bovenstaande oplossing is namelijk dat iedereen de moeder moet vertrouwen. Uiteindelijk kwam ik uit op een oplossing die zelfs de meest paranoia cryptograaf tevreden moet houden :).

  14. Jeanine:

    @ Johannes: gelukkig is mijn moeder erg betrouwbaar! :-) Ik verwacht vandaag of morgen mijn lootje met de post.

  15. Josine:

    @johannes: Doe mij dat pdfje maar. Lijkt me erg interessant.

  16. Sponzen Ridder:

    @jeanine: dat van dat betrouwen doet me denken aan een running gag die mijn vader elk jaar herhaalt. Na het trekken van de lotjes probeert hij zo vlug mogelijk van iedereen te weten wie wie getrokken heeft. Natuurlijk lukt dat niet, onze pokerface is ondertussen geoefend.

    Tot op het moment dat je iets vaags vertelt (bv: 'oei, weer den dienen om iets voor te zoeken!'). Dan springt hij triomfantelijk recht en roept: "Dat was het laatste wat ik nog nodig had om te weten wie jullie getrokken hadden."

    Als kind waren wij nooit helemaal zeker of het toch niet waar kon zijn. Elk jaar opnieuw.

  17. Rogier:

    @Johan: De kans dat iemand zichzelf niet trekt, ongeacht waar hij "in de rij" is, is (1 - 1/N).

    Dit tot de macht N, en N naar oneindig ...

    (of even zoeken op Wikipedia)

  18. Marleen:

    Alles is volkomen correct verlopen en de enveloppen zijn al op de plaatsen van bestemming aangekomen!

  19. Eva:

    Haha, dit hadden wij thuis ook gedaan! Later bleek dat m'n zusje ons al had opgegeven op http://www.lootjeschrijven.nl voor het trekken van de lootjes! Wel oppassen trouwens dat de lootjes op een zelfde manier gevouwen worden, of bij een envelop geen scheur etc!

  20. Johannes Verelst:

    @Josine Leuk dat er interesse is, bij deze dan:

    http://www.verelst.net/thesis.pdf

  21. Stefan:

    Beste Johannes,

    Ik heb even door je thesis gebladerd. Ik was vooral geïnteresseerd in de manier waarop je een permutatie zonder gefixeerde punten kiest. Je merkt terecht op dat je uniform uit al zulke permutaties zult moeten kiezen (iets wat met de enveloppen-doorschuifmethode en varianten daarop NIET gebeurt). Helaas gebruik je een randomized algoritme, dat je naar verwachting e keer moet uitvoeren. In het ergste geval moet je dus tot in de eeuwigheid doorwerken voordat je een resultaat krijgt.

    Heb je enig idee van de complexiteit van een algoritme dat gegarandeerd een geldige permutatie teruggeeft? Er staat me iets van bij dat het gegeneraliseerde probleem, waarbij sommige combinaties verboden zijn, #P-moeilijk is (i.e. je kunt weinig beters doen dan alle permutaties opschrijven, de geldige eruit vissen, en daaruit willekeurig 1 kiezen), maar dit geval heeft wel heel veel symmetrie!

  22. Koen:

    Hier ook een (onpraktische) oplossing:
    De moeder maakt voor de personen \(P_1, \ldots, P_n\) trekenveloppen \(T_1, \ldots, T_n\) en verstuurenveloppen \(V_1, \ldots, V_n\) met in trekenveloppe \(T_j\) alle namen behalve die van persoon \(P_j\). De moeder pakt (zonder te kijken) uit elke trekenveloppe \(T_j\) een naam en stopt die in de verstuurenveloppe \(V_j\). Dan gooit ze alle overgebleven namen uit alle trekenveloppen op een hoop, husselt ze door elkaar en kijkt of in de stapel elke naam even vaak (\(n-2\) keer) voorkomt. Als dat zo is dan verstuurt ze de verstuurenveloppen, anders probeert ze het opnieuw. Nadeel van deze methode is dat de kans van slagen (volgens mij) gelijk is aan \(\frac{(n-1)!}{(n-1)^n}\), en dat is voor \(n=6\) al \(\frac{24}{3124}\).

  23. Jobe:

    Hier volgt een "creatieve" oplossing die 100% werkt wanneer je de moeder vertrouwt dat ze niet spiekt. Je vraagt de moeder het volgende te doen:
    Reserveer voor iedere persoon een envelop met zijn naam erop. Noem het aantal personen n. Pak n briefjes en schrijf op het eerste briefje het woordje "ja". Vouw het dubbel (met het woordje "ja" aan de binnenkant) en schrijf de naam van persoon 1 aan de buitenkant. Voor de overige n-1 briefjes: schrijf op elk briefje "nee" en vouw het dubbel. Schrijf dan elk van de namen van persoon 2 t/m n op 1 van deze briefjes. Vervolgens niet je de n briefjes aan elkaar en heb je je eerste "boekje" gemaakt. Het tweede boekje maak je op een soortgelijke manier, alleen krijgt nu het briefje met de naam van persoon 2 een "ja" aan de binnenkant, en de andere briefjes van dit boekje een "nee". Zo ga je door en maak je n boekjes (elk bestaande uit n dubbelgevouwen briefjes). Nu vraag je de moeder om de boekjes te husselen en elk bij een envelop neer te leggen. Ze kan als volgt controleren of iemand zichzelf heeft: bij de envelop van persoon 1 opent ze van het bijbehorende boekje ALLEEN het briefje met de naam van persoon 1. Als er "ja" staat, kan ze opnieuw gaan husselen. Als er "nee" staat, gaat ze door met envelop 2. Hier kijkt ze natuurlijk alleen op het briefje van persoon 2 (een kwestie van voorzichtig bladeren). Staat er een "ja", kan ze opnieuw husselen. Staat er een "nee", kan ze door met envelop 3, etc. Als ze bij elke envelop een "nee" heeft aangetroffen, weet ze zeker dat niemand zichzelf heeft (zonder te weten wie wie heeft) en kan ze de boekjes in de bijbehorende enveloppen stoppen. (En verder aan ieder die meedoet vertellen wat de bedoeling is van die gekke boekjes ;-) )
    Het voordeel van deze methode is ook dat ze niet weet welke "kringetjes" van personen er ontstaan zijn.

  24. Jeanine:

    @Jobe: klopt. Het nadeel van jouw methode is dat het veel langer kan duren voor niemand zichzelf heeft, met de methode in mijn column gaat het zeker in 1 keer goed.

  25. Jobe:

    Dat is zeker waar, Jeanine. Mijn methode duurt naar verwachting even lang als de situatie dat iedere deelnemer gewoon aanwezig is voor een traditioneel trekken van lootjes.

  26. André van Delft:

    Ik heb een jaar geleden ook een stuk gewijd aan de Sinterklaaslootjes.
    Er bestaat een methode met enveloppen, pen en papier, die allerlei combinaties kan uitsluiten, zodat bijvoorbeeld niemand meer iemand anders toegewezen krijgt die hij het jaar daarvoor ook al had gehad.
    Oplossing: zie de link onder mijn naam.

  27. Gastspreker: het wiskundemeisje « Van alle markten thuis:

    [...] naar De man die kon rekenen en blijft het archief van Volkskrantcolumns een feest (deze bijvoorbeeld, of deze). En dan heb ik nog niet eens de rekenpuzzels genoemd. Maar ach, je kunt [...]

  28. Sinterklaas, loodjes trekken#$?!! | Oldenzaalnet.nl:

    [...] nog ouderwets met papiertjes doen. Zelfs als niet iedereen aanwezig is om te zelf te trekken. De Wiskundemeisjes van de Volkskrant doen het als [...]

  29. Festisite:

    Wat dachten jullie van http://www.festisite.com/lootjes-trekken/ ?

  30. Bart:

    Een variatie op het doorschuifalgoritme:
    Naam op briefjes. Naam op enveloppe.
    Briefjes met eigen naam in enveloppes.
    Enveloppen met namen naar beneden husselen.
    Dan: verdelen in willekeurige groepjes van elk ten minste twee en maximaal alle enveloppen.
    Dan in elke groep de briefjes 1 enveloppe doorschuiven. Dus zonder de naam op de briefjes en enveloppen te zien.

    Dan de enveloppen op 1 stapel, schudden en uitdelen.

  31. Jos:

    Er is nog een probleem met deze methode van doorschuiven: niet alle uitkomsten zijn mogelijk en sommige uitkomsten zijn waarschijnlijker dan andere (bij bepaalde aantallen personen). Probeer het maar eens met 4 personen (A, B, C en D). In theorie zijn er dan 9 mogelijke uitkomsten waarbij niemand zichzelf trekt:

    BADC
    BCDA
    BDAC
    CADB
    CDAB
    CDBA
    DABC
    DCAB
    DCBA

    De methode van doorschuiven leidt maar tot 6 mogelijke uitkomsten en mist BADC, CDAB en DCBA

    Helaas zijn er geen simpele manieren om een "derangement" van N personen (zoals deze wisselingen heten) te vinden waarbij (1) alle mogelijke wisselingen (2) even waarschijnlijk zijn .

  32. Teun:

    Als je twee lootjes per persoon wilt gebruiken, kun je ook deze methode gebruiken. Gewoon twee lootjes in elke envelop, en dan het ene lot één plaats doorschuiven en het andere lot twee plaatsen.

  33. Alexander Rinnooy Kan:

    Alweer een alternatief, maar misschien niet nieuw...?
    Opgevouwen papiertje met naam erop (maar niet leesbaar) in enveloppen met zelfde naam erop. Enveloppen permanent omdraaien (namen niet zichtbaar).
    Envelop (A) trekken, papiertje (A) eruit. Een van de andere enveloppen trekken (B). Papertje B daaruit, eerdere papiertje A in envelop B, opzij leggen (eerste toewijzing gerealiseerd).
    Eerdere envelop A terug in de stapel. Opnieuw envelop trekken. Is de nieuw getrokken envelop leeg, dan B erin en opnieuw beginnen. Zit er een papiertje in (C), dan de eerdere stap herhalen.
    Enig mogelijk probleem: uiteindelijk maar één envelop overhouden met een papiertje erin. Dat valt te vermijden door daarop te anticiperen als er nog maar twee enveloppen over zijn.
    Deze procedure genereert een willekeurige permutatie uit de verzameling van alle permutaties zonder cykels van lengte 1, zonder dat degene die de procedure uitvoert iets weet van de samenstelling ervan. Op elk moment zit er ten hoogste 1 lege envelop in de resterende collectie. Wordt die getrokken, dan sluit zich de lopende cykel.

Plaats een reactie


Je kunt LaTeX gebruiken in je reactie.
Gelieve antwoorden op puzzels tussen [SPOILER] en [/SPOILER] te plaatsen.