10Wie können wir unsere Methode praktikabler machen?

Sehr viel Arbeit für eine Person

Wenn $n$ Personen wichteln, brauchen wir mit der verbesserten Konjugations-Methode $2n-2$ Umschläge und in jedem Umschlag $n$ Karten. Also muss man insgesamt $n\cdot\left(2n-2\right)$ Karten schreiben.

Wir könnten die Karten am Computer erstellen und entsprechend oft drucken. Dadurch sparen wir uns das Beschriften der $n\cdot\left(2n-2\right)$ Karten und wir müssen diese Karten nur ausschneiden. Jedoch müssen wir für jeden Umschlag die entsprechende Permutation $\sigma$ oder $\varphi$ anwenden und mit einer Permutation konjugieren. Die Permutationen $\sigma$ und $\varphi$ sind gegeben durch

und

Konkret heißt das, wir mischen die Karten, schneiden sie auseinander, verschieben die Hälfte entsprechend der Permutation $\sigma$ oder $\varphi$ und kleben sie wieder zusammen.

Das ist immer noch viel Arbeit für eine Person.

Die Anzahl der Umschläge steigt linear mit der Anzahl der Personen. Deshalb wird es immer mehr Arbeit, je mehr Personen mitwichteln. Aber wir können die Arbeit auf alle Personen aufteilen: Jede Person erstellt zwei Umschläge, einen mit der Permutation $\sigma$ und einen mit der Permutation $\varphi$. Dann haben wir $n$ Umschläge je Permutation $\sigma$ und $\varphi$. Für das richtige Verhältnis brauchen wir aber $n-2$ Umschläge mit $\varphi$, also müssen wir $2$ Umschläge mit der Permutation $\varphi$ aussortieren. Wenn wir die Karten drucken, kann man durch die Handschrift nicht die Person erkennen. Dann müssen zwei Leute nur einen Umschlag mit der Permutation $\sigma$ erstellen.

Dadurch muss, egal wie viele Leute mitwichteln, jede Person höchstens $2$ Umschläge anfertigen. Leider steigt die Anzahl der Karten, die jeder ausschneiden muss, mit $n$. Also muss jeder $n$ oder $2n$ Karten vorbereiten.

Wiederverwenden der Umschläge

Neben dem hohen Aufwand hat die verbesserte Konjugations-Methode noch einen Nachteil: Weil wir nur einen Umschlag ziehen, haben wir sehr viele Umschläge und Karten, die nicht verwendet werden. Wir können sie auch nicht so einfach wiederverwenden. Denn wenn wir die unbenutzten Umschläge öffnen, würden wir herausfinden, welcher Umschlag für das Wichteln benutzt wurde. Wir müssten die ungeöffneten Umschläge also vernichten, was nicht sehr nachhaltig ist.

Wir können diesen Müll aber doch vermeiden: Wir sammeln alle Karten von dem benutzten Umschlag wieder ein, legen sie zurück in den Umschlag und verschließen diesen so, dass man ihn nicht von den anderen, unbenutzten unterscheiden kann. Dann kann man die Umschläge im nächsten Jahr wiederverwenden. Das geht aber nur, wenn wieder gleich viele Personen beim Wichteln mitmachen. Wenn mehr oder weniger mitwichteln, müssen wieder ganz neue Umschläge gebastelt werden.

Zusammenfassung

Wir haben verschiedene Methoden kennengelernt, die man zum Wichteln mit $n$ Teilnehmern benutzen kann.

Zum einen gibt es die klassische Wichtel-Methode. Dabei werden Zettel mit Namen aus einem Hut gezogen und so eine geheime Zuordnung von Wichteln (Schenkenden) zu Co-Wichteln (Beschenkten) erstellt. Mathematisch kann man eine solche Zuordnung als eine Permutation auf $\left\{1,\ldots,n\right\}$ auffassen. Der Nachteil dieser Methode ist, dass die durch das Ziehen der Zettel erzeugte Permutation möglicherweise nicht fixpunktfrei ist, also Personen ihren eigenen Namen ziehen können. Dann muss man die Ziehung wiederholen. Im Schnitt braucht man etwa drei Versuche.

Deshalb haben wir versucht, eine Methode zu finden, bei der man garantiert mit einer Ziehung auskommt. Unser erster Ansatz war die Briefumschlag-Methode. Dabei wählen wir statt aus allen Permutationen nur aus den fixpunktfreien Permutationen. Um die Zuordnung geheim zu halten, war es nötig, für jede fixpunktfreie Permutation einen Umschlag mit $n$ Karten zu erstellen, von denen einer ausgelost wird. Da aber die Anzahl der fixpunktfreien Permutationen mit steigender Teilnehmerzahl sehr schnell wächst, ist diese Methode nicht praktikabel - bei zehn Teilnehmern müsste man über eine Million Umschläge vorbereiten!

Eine andere Methode musste her. Dafür haben wir das Problem aus einem anderen Blickwinkel betrachtet und uns zuerst unsere Anforderungen an eine Wichtel-Methode vergegenwärtigt: Für jede Person soll, unter der Annahme, dass sie ihren Co-Wichtel kennt, die Wahrscheinlichkeit, von einem ihrer Mitspieler beschenkt zu werden, für jeden Mitspieler gleich groß sein. Bei der Briefumschlag-Methode haben wir das Problem durch schiere Masse erschlagen.

Die Konjugations-Methode dagegen startet mit einer festen fixpunktfreien Permutation und macht diese "zufälliger", indem die Zuordnung von Teilnehmern zu den Zahlen $\left\{1,\ldots,n\right\}$ durchmischt wird. Wir haben uns diese Methode für zwei fixpunktfreie Permutationen $\sigma$ und $\varphi$ angeschaut. Je nachdem, von welcher Permutation man ausgeht, ist jedoch die Wahrscheinlichkeit, vom eigenen Co-Wichtel beschenkt zu werden, entweder zu hoch oder zu niedrig.

Um den Wert $\frac{1}{n-1}$ zu erreichen, muss man die beiden Permutationen kombinieren und mit der passenden Wahrscheinlichkeit entweder $\sigma$ oder $\varphi$ beim Wichteln mit der Konjugations-Methode verwenden. Die Methode, die das tut, haben wir die verbesserte Konjugations-Methode genannt. Sie kombiniert die Konjugations- mit der Briefumschlag-Methode und ist unser bester Kandidat für eine Wichtel-Methode, bei der garantiert nur einmal gezogen werden muss:

1. Wir präparieren $n$ Briefumschläge mit der Konjugations-Methode mit $\sigma$ und $n-2$ Briefumschläge mit der Konjugations-Methode mit $\varphi$.

2. Wir werfen alle Umschläge in einen Hut (oder Ähnliches), mischen und ziehen einen Umschlag.

3. Die Karten dieses Umschlags werden nun wie bei der Briefumschlag-Methode ausgeteilt und verwendet.

Man braucht also bei $n$ Mitspielern nur $2n-2$ Umschläge. Diese Menge ist gut zu bewältigen, wenn man die Arbeit auf die Teilnehmer aufteilt und jeden zwei Umschläge (einen mit $\sigma$ und einen mit $\varphi$) vorbereiten lässt.

Wer hätte gedacht, dass mit so etwas Alltäglichem so viel interessante Mathematik treiben kann. Und wer würde jetzt noch behaupten, dass Mathematik nicht lebensnah ist!