Nogmaals: Sinterklaaslootjes trekken

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: