Vraag 13Lootjes trekken

Veel groepen en families trekken voor Sinterklaas of Kerstmis lootjes om te bepalen wie aan wie een cadeautje geeft. Het trekken van lootjes kan met behulp van papiertjes worden gedaan. Daarover gaat deze opgave. Dit lootjes trekken gaat als volgt: − Elke deelnemer schrijft de eigen naam op een papiertje. − Vervolgens worden deze zogenaamde lootjes in een zak gestopt. − Daarna trekt iedereen willekeurig blind één lootje uit de zak. Als iemand het eigen lootje trekt, moeten alle lootjes weer worden ingeleverd en worden de lootjes opnieuw getrokken. We noemen het trekken van lootjes anoniem als iedereen alleen de naam weet op het lootje dat hij/zij getrokken heeft en van geen enkel ander lootje kan beredeneren door wie het getrokken is. De verdeling van de lootjes over de verschillende personen noemen we goed als niemand het eigen lootje heeft en als het lootjes trekken anoniem is. We voeren de volgende notaties in: Z Minstens één persoon heeft het eigen lootje getrokken. A Het lootjes trekken is anoniem. G De verdeling van de lootjes is een goede verdeling. Gegeven is de zin: Als niemand het eigen lootje getrokken heeft en het lootjes trekken is anoniem, dan is de verdeling van de lootjes een goede verdeling.

Als de verdeling van de lootjes niet goed is, dan heeft minstens één persoon het eigen lootje getrokken en/of is het lootjes trekken niet anoniem. Met twee personen is er geen goede verdeling van lootjes mogelijk. Immers: − Als je je eigen lootje trekt, dan is de verdeling niet goed. Bovendien weet je dan ook dat de ander zichzelf heeft en is het daarmee ook niet anoniem. − Als je het lootje van de ander trekt, dan weet je dat de ander jouw lootje heeft getrokken en is het lootjes trekken niet anoniem. Ook voor drie personen is het niet mogelijk om een goede verdeling te krijgen. Sem, Finn en Rik gaan lootjes trekken.

Een groep van zes personen gaat lootjes trekken. Bij zes personen is lootjes trekken altijd anoniem, zolang mensen niet vertellen welk lootje zij getrokken hebben. In het vervolg van deze opgave hoef je dus geen rekening meer te houden met de anonimiteit. Een mogelijke verdeling van de lootjes is in de tabel weergegeven. tabel persoon P Q R S T U heeft het lootje getrokken van R P Q T U S Zonder het van elkaar te weten, vormen P , Q en R een subgroep binnen de groep van zes personen. De drie personen trekken in een soort kringetje elkaars lootje. Dit noemen we een kringetje van lengte 3 . Ook S , T en U vormen een kringetje van lengte 3. Omdat niemand het eigen lootje heeft, is er sprake van een goede verdeling. Met de notatie K wordt bedoeld dat er ten minste één kringetje van n lengte n aanwezig is in de verdeling van de lootjes. De volgende twee beweringen worden gedaan over het lootjes trekken met zes personen: − K ⇒ G 5 − K ∧ G ⇒ K 4 2

Vertaal elk van de twee beweringen naar een zin en geef van elke zin aan of de bewering waar is of niet. Licht je antwoord toe.