In het artikel Handig Sinterklaaslootjes toewijzen presenteerde ik een eenvoudige oplossing voor het bekende lootjes trekken, waarbij niemand zichzelf mag loten, en niemand de uitslag van de loting mag kennen.
Het gaat hier om een wiskundig probleem dat voor het eerst geformuleerd is door Alexander Rinnooy Kan.
Ik heb hem in 2007 of 2008 mijn oplossing voorgelegd. Hij liep niet over van enthousiasme, en dat was ook wel te verwachten. Mijn oplossing levert een permutatie (=verwisseling) op door als het ware een n-hoek één hoek te verdraaien. Er kunnen dus geen kleinere kringen zijn waarin men onderling elkaar heeft geloot.
Neem bijvoorbeeld bij n=4: mijn methode kan de volgende 6 permutaties opleveren:
2341 (dwz 1 loot 2; 2 loot 3, 3 loot 4 en 4 loot 1)
2413
3142
3431
4312
4123
De volgende 3 permutaties zijn wel toegestaan, maar met mijn methode niet mogelijk:
2143
3412
4321
En deze 15 permutaties zijn helemaal niet toegestaan, omdat steeds minstens 1 persoon zichzelf zou loten:
1234
1243
1324
1342
1423
1432
2134
2314
2431
3124
3214
3241
4132
4213
4231
Het totaal aantal permutaties hierboven is 24, en dat klopt (1*2*3*4=24).
Alexander Rinnooy Kan wilde eigenlijk een methode zien die niet alleen de bovenste 6 uitkomsten kan genereren, maar ook de 3 die eronder staan. Althans, dat voor het geval n=4. Voor andere n wil hij alle permutaties kunnen genereren voorzover die niemand zichzelf laat loten.
Er bestaat een supereenvoudige methode die aan Alexander’s wens tegemoet komt. Het is alleen meer werk, maar voor een wiskundige is dat soms niet belangrijk; in eerste instantie is de vraag of er zo’n methode bestaat.
De methode als volgt:
Iedere permutatie correspondeert een stapeltje enveloppen met namen erop en met briefjes erin waar ook de namen zijn geschreven. Maak voor iedere permutatie die je wil toestaan zo’n stapeltje enveloppen. Stop nu elk stapeltje in een grotere envelop. Stapel deze grotere enveloppen op elkaar, schud ze, en trek dan 1 van de grote enveloppen eruit. De inhoud van die envelop is een loting die je niet kent, en met precies de permutaties die je toestaat.
Je kan zelfs bepaalde permutaties afkeuren (bijvoorbeeld omdat een echtpaar elkaar niet zou mogen trekken); voor zo’n permutatie maak je geen stapeltje. Daartegenover kan je zelfs permutaties toestaan waarin sommigen zichzelf zouden loten, wanneer je dat zou willen. Of je kan sommige permutaties een grotere relatieve kans geven door die meerdere malen in de grotere enveloppes mee te laten loten. Je kan zo zelfs tot op elke willekeurige nauwkeurigheid een kansverdeling tussen de permutaties afdwingen. Dit hoort niet bij de oorspronkelijke probleemstelling, maar de methode geldt voor een grotere klasse van problemen.
Zo, en nu vragen wat Alexander Rinnooy Kan ervan vindt.
From Delft 
Leave a Reply