Dann ist Wichteln genau die richtige Option. Beim Wichteln bekommt jeder ein Geschenk von genau einer anderen Person aus der Gruppe. Dabei wird ausgelost, für wen man ein Geschenk besorgen soll. Außerdem soll es bis zum Schluss ein Geheimnis bleiben, von wem man beschenkt wurde.

Bildquelle: https://www.scribbler.com/

Normalerweise werden die Namen aller Beteiligten auf Zettel geschrieben und in einen Hut geworfen. Dann werden die Zettel im Hut gemischt und alle ziehen nacheinander einen Namen. Es kann jedoch passieren, dass eine Person sich selbst zieht, was natürlich nicht erwünscht ist - man soll sich ja nicht selbst beschenken. Eine übliche Lösung wäre: Die Person legt den Zettel in den Hut zurück und zieht einen neuen Namen. (Vorausgesetzt, es sind noch mindestens zwei Zettel im Hut - andernfalls muss neu gezogen werden.)

Daraus entsteht aber ein Problem: Die Informationen werden dadurch für diese Person erhöht.

Um dieses Problem zu verstehen, betrachten wir folgendes Beispiel: Angenommen, die Personen A, B, C und D wollen wichteln und ziehen in dieser Reihenfolge je einen Namen aus dem Hut. Falls A sich selbst zieht, ist das Zurücklegen noch nicht problematisch.

Nun hat A (ggf. nach ein paar Wiederholungen) einen Zettel mit dem Namen von B, C oder D gezogen und Person B ist an der Reihe. Was passiert, wenn Person B sich jetzt selbst zieht? B weiß dann, dass A den Namen von C oder D gezogen hat. Also kann Person B jetzt schließen, dass sie von C oder D beschenkt wird. Person B hat also mehr Informationen über ihren möglichen Wichtel als die anderen Personen.

Eine Möglichkeit zur Vermeidung dieses Problems wäre, dass man ganz von vorne beginnt, wenn eine Person sich selbst zieht. Jetzt stellt sich natürlich die Frage: Wie häufig müsste man dann im Schnitt ziehen, bis jede*r einen Namen gezogen hat, der nicht sein/ihr eigener ist?

Um dies herauszufinden, wollen wir die Situation in mathematische Sprache verwandeln.

Wir müssen erstmal die Gruppe von Teilnehmern mathematisch repräsentieren. Nehmen wir an, dass beim Wichteln $nn$ Personen mitmachen wollen, wobei $nn$ eine beliebige natürliche Zahl (und am besten größer als $11$) ist. Dann können wir jeder Person eine Zahl zwischen $11$ und $nn$ zuweisen und die gesamte Gruppe als die Menge $\{1,\dots ,n\}\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ beschreiben. (Natürlich könnte man die Teilnehmer-Gruppe auch durch jede andere $nn$-elementige Menge beschreiben, jedoch ist $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ die einfachste solche.)

Beim Wichteln soll jede Person genau einer anderen Person etwas schenken, sodass am Ende alle ein Geschenk bekommen. Wir nennen dabei die Person, die etwas verschenkt, den Wichtel und die, die etwas geschenkt bekommt, den Co-Wichtel. Da jeder Teilnehmer ein Wichtel sein soll, wollen wir jeder Person $k\in \{1,\dots ,n\}k\backslash \; \backslash in\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ eine Person $k^{\mathrm{\prime }}\in \{1,\dots ,n\}k\text{'}\backslash \; \backslash in\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ zuordnen, der sie etwas schenken soll. Dann ist $k^{\mathrm{\prime }}k\text{'}$ der Co-Wichtel von $kk$. Diese Zuordnung ist nichts anderes als eine Funktion von der Menge $\{1,\dots ,n\}\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ in sich selbst. Wir symbolisieren sie mit dem Buchstaben $\sigma \backslash sigma$ („sigma“):

Diese Funktion muss noch weitere Eigenschaften haben, wenn sie die Zuordnung von Wichteln zu Co-Wichteln beschreiben soll:

• Jede Person soll ein Co-Wichtel von jemandem sein (jeder soll ein Geschenk bekommen), d.h. für jedes $k^{\mathrm{\prime }}\in \{1,\dots ,n\}k\text{'}\backslash \; \backslash in\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ soll es ein $k\in \{1,\dots ,n\}k\backslash \; \backslash in\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ geben mit $\sigma \left(k\right)=k^{\mathrm{\prime }}\backslash sigma\backslash left(k\backslash right)\backslash \; =\backslash \; k\text{'}$. Eine Funktion mit dieser Eigenschaft heißt surjektiv.

• Kein Wichtel soll sein eigener Co-Wichtel sein (niemand soll sich selbst ein Geschenk machen), d.h. für alle $k\in \{1,\dots ,n\}k\backslash \; \backslash in\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ soll $\sigma \left(k\right)\mathrm{\ne }k\backslash sigma\backslash left(k\backslash right)\backslash \; \backslash ne\; k\backslash$ gelten. Eine Funktion mit dieser Eigenschaft heißt fixpunktfrei.

Eine surjektive Funktion $\sigma \text{\hspace{0.17em}⁣}:\{1,\dots ,n\}\to \{1,\dots ,n\}\backslash sigma\backslash colon\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}\backslash to\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ zwischen endlichen Mengen mit gleich vielen Elementen hat automatisch auch die Eigenschaft, dass kein $k^{\mathrm{\prime }}\in \{1,\dots ,n\}k\text{'}\backslash \; \backslash in\backslash \; \backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ mehr als einmal von $\sigma \backslash sigma$ getroffen wird, d.h. dass kein Co-Wichtel mehr als ein Geschenk erhält. Eine Funktion mit dieser Eigenschaft heißt injektiv. Eine Funktion, die injektiv und surjektiv ist, heißt bijektiv. Wir geben den bijektiven Funktionen auf $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ einen speziellen Namen.

Fassen wir zusammen: Wir haben die Gruppe von Teilnehmern durch die Menge mit den Elementen $11$ bis $nn$ beschrieben. Das Wichteln modellieren wir durch eine Funktion dieser Menge in sich selbst. Damit es so funktioniert, wie wir es wollen, können wir jedoch nicht jede beliebige Funktion hernehmen, sondern suchen nach einer fixpunktfreien Permutation.

Natürlich könnten wir jetzt eine beliebige fixpunktfreie Permutation $\sigma \backslash sigma$ auf $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ wählen und diese zum Wichteln benutzen. Dafür würden wir festlegen, dass jede Person $k\in \{1,\dots ,n\}k\backslash in\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ der Person $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ ein Geschenk machen soll. Allerdings wäre es witzlos, wenn alle Teilnehmer die Permutation kennen: Dann weiß jeder, wer wem etwas schenkt. Wir wollen also eine Methode finden, um eine fixpunktfreie Permutation zufällig auszuwählen, sodass jeder Teilnehmer nur weiß, wem er selbst etwas schenken muss, und sonst nichts über die Permutation bekannt ist. Üblicherweise wird das durch Ziehen von Namenszetteln aus einem Hut erreicht. Die dabei entstehende Permutation (d.h. bijektive Zuordnung zwischen den Teilnehmern) ist aber unter Umständen nicht fixpunktfrei, nämlich dann, wenn eine Person ihren eigenen Namen zieht. Als Nächstes wollen wir uns deshalb überlegen, wie wahrscheinlich es ist, dass das passiert.

Wir haben uns schon überlegt, wie wir Wichteln mathematisch beschreiben können: Gesucht ist eine fixpunktfreie Permutation der Mitspieler, also eine bijektive Abbildung $\sigma \text{\hspace{0.17em}⁣}:\{1,\dots ,n\}\to \{1,\dots ,n\}\backslash sigma\backslash colon\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}\backslash to\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ ohne Fixpunkte. Das heißt, es soll $\sigma \left(k\right)\mathrm{\ne }k\backslash sigma\backslash left(k\backslash right)\backslash ne\; k$ für alle $k\in \{1,\dots ,n\}k\backslash in\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ gelten. Üblicherweise versucht man, eine Permutation durch Ziehen von Namenszetteln aus einem Hut zu erzeugen: Das entspricht genau einer bijektiven Zuordnung zwischen Wichteln (das sind die Personen $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$) und Co-Wichteln (ebenfalls die Personen $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$). Die so entstandene Permutation ist aber nicht fixpunktfrei, wenn eine Person ihren eigenen Namen zieht. In diesem Fall muss man neu ziehen. Aber wie wahrscheinlich ist es eigentlich, dass das passiert?

Wir gehen davon aus, dass die Namenszettel im Hut gut gemischt sind. Dann liefert jede Ziehung von Namen aus dem Hut mit gleicher Wahrscheinlichkeit eine der $n!n!$ möglichen Permutationen. Es handelt sich hier also um ein Urnenmodell: Aus den $n!n!$ möglichen Permutationen wird durch eine Ziehung gleichverteilt eine ausgewählt. Wenn wir wissen wollen, wie wahrscheinlich es ist, dass die durch die Ziehung bestimmte Permutation fixpunktfrei ist, müssen wir uns zunächst überlegen, wie viele fixpunktfreie Permutationen von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ es gibt.

Beispiel. Für $n=1n=1$ ist die einzig mögliche Permutation die Abbildung $\sigma :\left\{1\right\}\to \left\{1\right\}\backslash sigma:\backslash left\backslash \{1\backslash right\backslash \}\backslash to\backslash left\backslash \{1\backslash right\backslash \}$, welche $11$ auf $11$ abbildet. Diese ist nicht fixpunktfrei. Für $n=2n=2$ gibt es zwei mögliche Permutationen: Erstens die Permutation ${\sigma }_1:\left\{\mathrm{1,2}\right\}\to \left\{\mathrm{1,2}\right\}\backslash sigma\_1:\backslash left\backslash \{1\{,\}2\backslash right\backslash \}\backslash to\backslash left\backslash \{1\{,\}2\backslash right\backslash \}$ mit ${\sigma }_1\left(1\right)=1\backslash sigma\_1\backslash left(1\backslash right)=1$ und ${\sigma }_1\left(2\right)=2\backslash sigma\_1\backslash left(2\backslash right)=2$, und zweitens die Permutation ${\sigma }_2:\left\{\mathrm{1,2}\right\}\to \left\{\mathrm{1,2}\right\}\backslash sigma\_2:\backslash left\backslash \{1\{,\}2\backslash right\backslash \}\backslash to\backslash left\backslash \{1\{,\}2\backslash right\backslash \}$ mit ${\sigma }_2\left(1\right)=2\backslash sigma\_2\backslash left(1\backslash right)=2$ und ${\sigma }_2\left(2\right)=1\backslash sigma\_2\backslash left(2\backslash right)=1$. Von diesen ist die zweite fixpunktfrei, die erste nicht. Es gibt also genau eine fixpunktfreie Permutation. Von den sechs möglichen Permutationen im Fall $n=3n=3$ sind nur zwei Permutationen ${\sigma }_1,{\sigma }_2\backslash sigma\_1,\backslash sigma\_2$ fixpunktfrei, wobei ${\sigma }_1\left(1\right)=2\backslash sigma\_1\backslash left(1\backslash right)=2$, ${\sigma }_1\left(2\right)=3\backslash sigma\_1\backslash left(2\backslash right)=3$, ${\sigma }_1\left(3\right)=1\backslash sigma\_1\backslash left(3\backslash right)=1$ bzw. ${\sigma }_2\left(1\right)=3\backslash sigma\_2\backslash left(1\backslash right)=3$, ${\sigma }_2\left(2\right)=1\backslash sigma\_2\backslash left(2\backslash right)=1$, ${\sigma }_2\left(3\right)=2\backslash sigma\_2\backslash left(3\backslash right)=2$.

Allgemein gilt: Die Anzahl $d_{n}d\_n$ der fixpunktfreien Permutationen von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ ist

Das kann man mithilfe des sogenannten Einschluss-Ausschluss-Prinzips berechnen, wie du zum Beispiel auf Wikipedia nachlesen kannst. Weil es insgesamt $n!n!$ Permutationen von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ gibt, beträgt der Anteil der fixpunktfreien Permutationen somit

Da beim Ziehen aus dem Hut jede Permutation mit der gleichen Wahrscheinlichkeit herauskommen kann, ist die Wahrscheinlichkeit $p_{n}p\_n$, dass die zufällig gezogene Permutation von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ fixpunktfrei ist, genau der Anteil der fixpunktfreien Permutationen. Es gilt also $p_n=\frac{d_n}{n!}p\_n=\backslash frac\{d\_n\}\{n!\}$.

Beispiel. Für die Menge $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$, $n\le 10n\backslash le10$, zeigt die Tabelle die Anzahl $d_{n}d\_n$ der fixpunktfreien Permutationen, die Anzahl $n!n!$ aller möglichen Permutationen und den Anteil $p_n=\frac{d_n}{n!}p\_n=\backslash frac\{d\_n\}\{n!\}$ der fixpunktfreien Permutationen (Quelle: Wikipedia):

Nun können wir für eine gegebene feste Teilnehmerzahl $nn$ berechnen, was die erwartete Anzahl an Ziehungen ist, die notwendig sind, um eine fixpunktfreie Permutation zu erwischen. Die Wahrscheinlichkeit, eine fixpunktfreie Permutation zu erwischen, bleibt in jeder Ziehung gleich und beträgt $p_{n}p\_n$. Mithilfe der sogenannten geometrischen Verteilung kann man sich überlegen, dass die erwartete Anzahl an benötigten Ziehungen gleich $\frac{1}{p_n}\backslash frac\{1\}\{p\_n\}$ ist. Intuitiv ergibt das Sinn: Wenn beispielsweise die Wahrscheinlichkeit für das Eintreten eines bestimmten Ergebnisses $\frac{1}{3}\backslash frac\{1\}\{3\}$ beträgt, dann erwarten wir, dass „im Durchschnitt“ drei, also $\frac{1}{\frac{1}{3}}\backslash frac\{1\}\{\backslash frac\{1\}\{3\}\}$ Versuche nötig sind, um dieses Ergebnis zu erzielen.

Beispiel. Aufbauend auf der vorherigen Tabelle, können wir für $n\le 10n\backslash le10$ die erwartete Anzahl $\frac{1}{p_n}=\frac{n!}{d_n}\backslash frac\{1\}\{p\_n\}=\backslash frac\{n!\}\{d\_n\}$ an benötigten Ziehungen angeben. Den Fall $n=1n=1$ müssen wir natürlich weglassen, da ja die Wahrscheinlichkeit $p_{1}p\_1$, eine fixpunktfreie Permutation von $\left\{1\right\}\backslash left\backslash \{1\backslash right\backslash \}$ zu ziehen, gleich null ist.

Wenn wir die Werte für $\frac{1}{p_n}\backslash frac\{1\}\{p\_n\}$ auf eine ganze Zahl runden, erhalten wir, dass im Schnitt etwa drei Ziehungen nötig sind, bis man eine fixpunktfreie Permutation erwischt! Wir wollen uns nun eine Methode überlegen, mit der man garantiert nur eine Ziehung braucht, um jedem Wichtel seinen Co-Wichtel zuzuordnen.

Mit der „klassischen“ Wichtel-Methode (Ziehen von Zetteln aus einem Hut) muss man im Schnitt etwa dreimal neu ziehen, bis niemand sich selbst zugeordnet bekommt. Wir wollen uns jetzt eine andere Methode überlegen, bei der man garantiert nur einmal ziehen muss.

Die Methode soll nach wie vor „geheim“ sein: Niemand soll Informationen darüber haben, von wem er oder sie beschenkt wird. Und natürlich soll auch niemand sich selbst beschenken müssen. Mit anderen Worten: Wir wollen wieder eine fixpunktfreie Permutation

finden, sodass jeder Mitspieler $kk$ nur seinen Co-Wichtel $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ kennt und keine Information über seinen Wichtel ${\sigma }^{-1}(k)\backslash sigma^\{-1\}(k)$ hat.

Durch das Ziehen aus dem Hut haben wir mit gleicher Wahrscheinlichkeit aus allen möglichen Permutationen ausgewählt. Aber weil sich darunter auch Permutationen mit Fixpunkten befinden, muss man möglicherweise neu ziehen. Wie wäre es, wenn wir stattdessen nur aus den fixpunktfreien Permutationen auswählen?

Stellen wir uns vor, dass wir alle fixpunktfreien Permutationen von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ in eine Urne stecken, mischen, eine Permutation $\sigma \backslash sigma$ ziehen und diese zum Wichteln benutzen. Das Problem ist, dass keiner der Mitspieler die Permutation kennen darf. Sonst wüssten ja alle, wer wem ein Geschenk macht. Wir brauchen also eine Methode, wie wir jedem Wichtel $kk$ seinen Co-Wichtel $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ mitteilen können, ohne dass sich eine Person die ganze Permutation anschauen muss und dadurch mehr Information als die anderen erhält.

Eine Permutation $\sigma \text{\hspace{0.17em}⁣}:\{1,\dots ,n\}\to \{1,\dots ,n\}\backslash sigma\backslash colon\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}\backslash to\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ können wir definieren oder aufschreiben, indem wir für jede Zahl $k\in \{1,\dots ,n\}k\backslash in\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ angeben, was das zugehörige $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ ist. Das geht zum Beispiel in Form einer Tabelle:

Zum Beispiel gehört zu der fixpunktfreien Permutation $\sigma \text{\hspace{0.17em}⁣}:\{\mathrm{1,2},3\}\to \{\mathrm{1,2},3\}\backslash sigma\backslash colon\backslash \{1\{,\}2,3\backslash \}\backslash to\backslash \{1\{,\}2,3\backslash \}$ mit $\sigma (1)=2\backslash sigma(1)=2$, $\sigma (2)=3\backslash sigma(2)=3$ und $\sigma (3)=1\backslash sigma(3)=1$ die Tabelle

Auf diese Weise könnten wir jede der fixpunktfreien Permutationen von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ auf einen Zettel schreiben und anschließend zufällig eine davon ziehen. Nun soll aber niemand die ganze gezogene Permutation $\sigma \backslash sigma$ kennen. Deshalb wollen wir es so einrichten, dass nach der Ziehung einer der fixpunktfreien Permutationen jede Person nur eine Spalte der Tabelle der Form

bekommt. Das können wir zum Beispiel dadurch erreichen, indem wir vor der Ziehung die Spalten jeder zu einer Permutation gehörenden Tabelle mit einer Schere trennen und jede so in ihre Spalten zerlegte Permutation in einen eigenen Umschlag stecken. Der zur obigen Permutation von $\{\mathrm{1,2},3\}\backslash \{1\{,\}2,3\backslash \}$ gehörende Briefumschlag würde beispielsweise die drei Karten

enthalten.

Anschließend wird einer der Umschläge gezogen (also eine fixpunktfreie Permutation $\sigma \backslash sigma$ zufällig ausgewählt) und jeder Mitspieler zieht genau eine der Tabellenspalten aus dem Umschlag. Dann weiß jede Person von nur einem $k\in \{1,\dots ,n\}k\backslash in\backslash \{1,\backslash ldots,n\backslash \}$, was das zugehörige $\sigma (k)\backslash sigma(k)$ ist. Das ist schon fast, was unser Ziel war: Nun müssen wir nur noch jeder Person ihre Nummer $kk$ zuordnen, also die Nummer, die auf der oberen Hälfte ihrer gezogenen Karte steht. Das geht zum Beispiel, indem jede Person ihren Namen in eine Tabelle einträgt, die für alle einsehbar ist.

Allgemein können wir diese Methode für $nn$ Mitspieler folgendermaßen zusammenfassen:

1. Wir suchen uns alle fixpunktfreien Permutationen von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ heraus.

2. Für jede dieser Permutationen $\sigma \backslash sigma$ bereiten wir ein Set aus $nn$ Zetteln oder Karten vor:

   1. Die obere Hälfte jeder Karte wird mit einer der Zahlen aus $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ beschriftet.

   2. Für $k\in \{1,\dots ,n\}k\backslash in\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ wird auf die untere Hälfte der mit $kk$ beschrifteten Karte der Wert $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ geschrieben.

3. Jedes Kartenset stecken wir jeweils in einen anonymen Briefumschlag.

4. Aus den Briefumschlägen wird zufällig einer gezogen. Die übrigen werden versteckt oder vernichtet.

5. Jeder Mitspieler zieht eine Karte aus dem Briefumschlag (die niemand sonst sehen darf).

6. Es wird eine für alle sichtbare Zuordnung „Zahl $\leftrightarrow \backslash leftrightarrow$ Person“ erstellt, z.B. in Form einer Tabelle:

   1. Die linke Spalte enthält die Zahlen von $11$ bis $nn$.

   2. In die rechte Spalte werden Namen eingetragen: Die Person, die auf der oberen Hälfte ihrer Karte die Zahl $kk$ stehen hat, schreibt ihren Namen in der Tabelle in die Zeile $kk$.

7. Jede Person schaut in der Tabelle nach, wer ihr Co-Wichtel ist: Person $kk$ (deren Karte auf der oberen Hälfte mit $kk$ beschriftet ist), schaut auf die untere Hälfte ihrer Karte, sieht dort die Zahl $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ ihres Co-Wichtels und findet durch einen Blick auf die Tabelle heraus, welche Person das ist.

Wir wollen dieses Vorgehen die Briefumschlag-Methode nennen. Sie tut genau, was wir uns wünschen: Es ist nur eine Ziehung notwendig und jede Person kennt nur ihren Co-Wichtel und hat sonst keine Informationen darüber, wer wem etwas schenkt. Die Sache hat nur einen Haken: Es müssen viele Umschläge und Karten vorbereitet werden.

Erinnern wir uns, dass es bei $nn$ Mitspielern $d_n=n!{\sum }_{k=0}^n\frac{{(-1)}^k}{k!}d\_n=n!\backslash sum\_\{k=0\}^n\backslash frac\{\backslash left(-1\backslash right)^k\}\{k!\}$ fixpunktfreie Permutationen gibt. Für jede Permutation muss ein Umschlag vorbereitet werden, der jeweils $nn$ beschriftete Karten enthält. Die Fakultät in der Formel deutet es schon an: Die Zahlen $d_{n}d\_n$ werden für wachsende Teilnehmerzahl $nn\backslash$sehr schnell sehr groß:

Schon bei sechs Mitspielern muss man somit $265265$ Umschläge mit jeweils $66$ Karten vorbereiten und insgesamt $15901590$ Karten beschriften! Die Briefumschlag-Methode ist somit leider nicht wirklich praktikabel. Aber vielleicht können wir sie modifizieren, um die Anzahl der benötigten Umschläge und Karten zu verringern? Dafür wollen wir das Problem aus einem etwas anderen Blickwinkel betrachten.

Bei der vorherigen Methode haben wir jede fixpunktfreie Permutation in Form eines Umschlags angefertigt und dann aus allen Umschlägen einen gezogen. Aber vielleicht können wir es vermeiden, alle fixpunktfreien Permutationen erzeugen zu müssen. Dafür wollen wir das Problem anders betrachten und zunächst überlegen, welche Eigenschaften unsere Methode für das Wichteln eigentlich erfüllen soll.

Wir wissen schon, dass wir auf irgendeine Weise eine fixpunktfreie Permutation $\sigma \backslash sigma$ auf der Menge $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ der Teilnehmer generieren müssen. Dabei soll niemand sich selbst beschenken, also soll $\sigma \backslash sigma$ fixpunktfrei sein. Und natürlich sollte die Methode jeder Person $kk$ ihren Co-Wichtel $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ mitteilen.

Außerdem darf niemand Informationen darüber haben, wer ihn beschenkt. Also soll die Wahrscheinlichkeit, von einer bestimmten anderen Person beschenkt zu werden, für alle Personen gleich groß sein. Anders gesagt: Wenn Person $kk$ weiß, dass ihr Co-Wichtel Person $k^{\mathrm{\prime }}k\text{'}$ ist, dann soll die Wahrscheinlichkeit, dass $kk$ von irgendeinem ihrer $n-1n-1$ Mitspieler beschenkt wird, für jeden Mitspieler $ll$ gleich groß sein. Mathematisch ausgedrückt ist das eine bedingte Wahrscheinlichkeit: Gegeben $\sigma \left(k\right)=k^{\mathrm{\prime }}\backslash sigma\backslash left(k\backslash right)=k\text{'}$ soll die Wahrscheinlichkeit für $\sigma \left(l\right)=k\backslash sigma\backslash left(l\backslash right)=k$ gleich $\frac{1}{n-1}\backslash frac\{1\}\{n-1\}$ für alle $l\mathrm{\ne }kl\backslash ne\; k$ sein. In Formeln:

Bei der Briefumschlag-Methode wird die zweite Eigenschaft mit den Wahrscheinlichkeiten dadurch erfüllt, dass wir aus allen fixpunktfreien Permutationen losen. Leider sind das so viele, dass wir die ganzen Umschläge nicht mehr erstellen können.

Wir können das Problem aber auch andersherum angehen. Anstatt alle fixpunktfreien Permutationen zu erzeugen, starten wir mit nur einer fixpunktfreien Permutation $\sigma \backslash sigma$. Diese ist allen bekannt. Dann brauchen wir minimal viele Umschläge, und zwar keinen, da wir nur eine Permutation haben und keine mehr auszulosen brauchen. Weil aber jeder die Permutation kennt, sind wir maximal weit von unserem Ziel entfernt, dass niemand Informationen darüber hat, wer wen beschenkt.

Wie können wir davon ausgehend die Permutation $\sigma \backslash sigma$ zufälliger machen?

Angenommen wir haben eine fixpunktfreie Permutation $\sigma :\{1,\dots ,n\}\to \{1,\dots ,n\}\backslash sigma:\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}\backslash to\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ gegeben, ordnen jedem Mitspieler eine der Zahlen von $11$ bis $nn$ zu und benutzen $\sigma \backslash sigma$ zum Wichteln. Das heißt, Person $kk$ soll der Wichtel von Person $\sigma \left(k\right)\backslash sigma\backslash left(k\backslash right)$ sein. Wenn nun ein Teilnehmer die ganze Permutation $\sigma \backslash sigma$ kennt, kann er ihre Inverse ${\sigma }^{-1}\backslash sigma^\{-1\}$ (die Umkehrfunktion von $\sigma \backslash sigma$) bestimmen und damit herausfinden, wer sein Wichtel ist. Deshalb können wir nicht einfach allen Teilnehmern ihre Nummer und die Permutation $\sigma \backslash sigma$ mitteilen, sondern müssen die Zuordnung „zufälliger“ gestalten, indem wir eine der Informationen unbekannt machen.

Die Permutation $\sigma \backslash sigma$ zu kennen kann den Mitspielern nur dann etwas über ihre (Co-)Wichtel verraten, wenn alle wissen, wem welche Zahl zugeordnet ist. Ohne diese Information ist es für eine Person nicht möglich, ihren Wichtel oder Co-Wichtel herauszufinden. Damit können wir etwas über die Zuordnung von Wichteln zu Co-Wichteln unbekannt machen: Wir wollen eine Methode finden, um jeder Person $kk$ ihren Co-Wichtel $\sigma (k)\backslash sigma(k)$ zuzuordnen, ohne dass bekannt wird, welcher Person welche Nummer zugeordnet war. Wie können wir das anstellen?

Eine Möglichkeit wäre, die Personen $\{1,\dots ,n\}\backslash \{1,\; \backslash dots,\; n\backslash \}$ zunächst durchzumischen, also alle Teilnehmer auf zufällige Art und Weise „umzubenennen“, indem wir ihnen neue Zahlen $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ zuweisen. Dann wenden wir $\sigma \backslash sigma$ auf diese neue Reihenfolge an.

Weil $\sigma \backslash sigma$ bekannt ist, kann man zwar immer noch ${\sigma }^{-1}\backslash sigma^\{-1\}$ berechnen, aber man weiß nicht mehr, zu welcher Person die Zahl ${\sigma }^{-1}(k)\backslash sigma^\{-1\}(k)$ gehört. Damit haben wir die Zuordnung von Wichteln zu Co-Wichteln zufälliger gemacht. Die Frage ist nun, wie wir das praktisch durchführen können.

Wir betrachten jeden Wichtel als eine Karte. Diese Karten drehen wir um, mischen sie und bringen sie (immer noch verdeckt) in eine Reihenfolge. Nun möchten wir auf diese neue verdeckte Reihenfolge die Permutation $\sigma \backslash sigma$ anwenden. Wir können nicht einfach die Karten neu anordnen, da wir so vergessen, zu welchem Wichtel der ursprüngliche Platz gehört.

Wenn wir die Information, welcher Wichtel auf der Karte ist, zweimal schreiben, können wir die Karten nach dem Mischen durchschneiden und $\sigma \backslash sigma$ auf eine Hälfte der Karten anwenden (zum Beispiel die obere Hälfte jeder Karte).

Nun müssen wir die Karten nur wieder dem echten Wichteln $\{1,\dots ,n\}\backslash \{1,\; \backslash dots,\; n\backslash \}$ zuordnen, damit jeder Wichtel seinen Co-Wichtel erfährt. Das können wir in der Praxis nun ganz einfach machen: (Unsere Wichtel heißen ja in der Realität anders als $1,\dots ,n1,\; \backslash dots,\; n$.). Wir kleben die neu sortierten Karten wieder zusammen, schmeißen sie in einen Hut und jeder zieht sich eine Karte. Auf jeder Karte steht nun, welche Zahl $1,\dots ,n1,\; \backslash dots,\; n$ er selbst ist und welche Zahl $1,\dots ,n1,\; \backslash dots,\; n$ sein Co-Wichtel ist. Wir müssen damit nur noch eine Liste anlegen, auf der steht, welche Zahl zu welcher Person korrespondiert.

Diesen Vorgang bezeichnen wir als Konjugations-Methode.

Um die Konjugationsmethode zu verwenden, benötigen wir eine fixpunktfreie Permutation $\sigma \backslash sigma$. Eine einfache fixpunktfreie Permutation ist die Abbildung, welche die Elemente von $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ „zyklisch“ um eine Position verschiebt, d.h. die Abbildung $\sigma \text{\hspace{0.17em}⁣}:\{1,\dots ,n\}\to \{1,\dots ,n\}\backslash sigma\backslash colon\; \backslash \{1,\; \backslash dots,\; n\backslash \}\; \backslash to\; \backslash \{1,\; \backslash dots,\; n\backslash \}$, die der Tabelle

entspricht.

Erinnern wir uns an das Ziel, das wir mit unserer Wichtelmethode erreichen wollen: Wir wollen, dass die bedingte Wahrscheinlichkeit $P({\sigma }^{\mathrm{\prime }}(i)=k\mid {\sigma }^{\mathrm{\prime }}(k)=k^{\mathrm{\prime }})=\frac{1}{n-1}P(\backslash sigma\text{'}(i)=k\backslash mid\backslash sigma\text{'}(k)=k\text{'})=\backslash frac\{1\}\{n-1\}$ für jedes $i\mathrm{\ne }ki\; \backslash ne\; k$ ist. Mit anderen Worten, die Wahrscheinlichkeit, dass man von einem gewissen Mitspieler beschenkt wird, soll für alle Mitspieler gleich groß sein, gegeben, dass man weiß, wer der eigene Co-Wichtel ist. Haben wir dieses Ziel erreicht, wenn wir $\sigma \backslash sigma$ mit der Konjugationsmethode zu einer Permutation ${\sigma }^{\mathrm{\prime }}\backslash sigma\text{'}$ zufällig ändern?

Wenn wir $\sigma \backslash sigma$ auf eine Karte $kk$ anwenden und die Karte $k^{\mathrm{\prime }}k\text{'}$ erhalten, kann $k^{\mathrm{\prime }}k\text{'}$ durch $\sigma \backslash sigma$ nicht auf $kk$ geschickt werden. Zumindest, wenn wir mit mindestens $33$ Karten arbeiten. Damit ist für $n\ge 3n\; \backslash ge\; 3$ die Wahrscheinlichkeit $P({\sigma }^{\mathrm{\prime }}(k^{\mathrm{\prime }})=k\mid {\sigma }^{\mathrm{\prime }}(k)=k^{\mathrm{\prime }})=0P(\backslash sigma\text{'}(k\text{'})=k\backslash mid\backslash sigma\text{'}(k)=k\text{'})=0$ und $k^{\mathrm{\prime }}k\text{'}$ nie der Wichtel von $kk$. Weil wir mischen, kann aber jede andere Person, die nicht $kk$ oder $k^{\mathrm{\prime }}k\text{'}$ entspricht, der Wichtel von $kk$ sein. Von diesen gibt es $n-2n-2$ viele. Wir erhalten also

Damit stimmen die Wahrscheinlichkeiten nicht mit den gewünschten überein: Die Wahrscheinlichkeit, dass man von einer bestimmten anderen Person beschenkt wird, ist mit $00$ zu klein, wenn man ihr Wichtel ist, und mit $\frac{1}{n-2}\backslash frac\{1\}\{n-2\}$ zu groß, wenn man nicht ihr Wichtel ist.

Eine andere Permutation

Wenn die Wahrscheinlichkeit, jemandes Co-Wichtel zu sein, für alle Personen (außer einem selbst) gleich sein soll, müssen wir also eine andere Permutation ausprobieren. Das Problem ist, dass $\sigma \backslash sigma$ es nicht zulässt, von seinem eigenen Co-Wichtel als Co-Wichtel gezogen zu werden. Wir benötigen also eine Permutation, auf die das zutrifft. Was muss eine solche Permutation $\phi \backslash varphi$ erfüllen? Es soll eine Person $ii$ geben, deren Co-Wichtel $\phi \left(i\right)\backslash varphi\backslash left(i\backslash right)$ der Wichtel von $ii$ selbst ist. Es soll also ein $ii$ geben, sodass $\phi (\phi (i))=i\backslash varphi(\backslash varphi(i))\; =\; i$ gilt.

Eine einfache solche Permutation $\phi \text{\hspace{0.17em}⁣}:\{1,\dots ,n\}\to \{1,\dots ,n\}\backslash varphi\backslash colon\backslash \{1,\backslash dots,\; n\backslash \}\; \backslash to\; \backslash \{1,\backslash dots,\; n\backslash \}$ können wir für $n\ge 4n\; \backslash ge\; 4$ durch die folgende Tabelle bauen:

Wie sehen die Wahrscheinlichkeiten für diese Permutation aus? Wir haben durch die Konjugationsmethode mit $\phi \backslash varphi$ eine Permutation ${\phi }^{\mathrm{\prime }}\backslash varphi\text{'}$ erhalten und diese hat ${\phi }^{\mathrm{\prime }}(k)=k^{\mathrm{\prime }}\backslash varphi\text{'}(k)\; =\; k\text{'}$. Wenn die Karte $kk$ beim Mischen zur ersten oder zweiten Karte wird, ist der Wichtel von $kk$ sicher $k^{\mathrm{\prime }}k\text{'}$. Dies passiert mit der Wahrscheinlichkeit $\frac{2}{n}\backslash frac\; 2n$. Wenn $kk$ beim Mischen zu irgendeiner anderen Karte wird, ist $k^{\mathrm{\prime }}k\text{'}$ nie der Wichtel von $kk$. Somit haben wir $P({\phi }^{\mathrm{\prime }}(k^{\mathrm{\prime }})=k\mid {\phi }^{\mathrm{\prime }}(k)=k^{\mathrm{\prime }})=\frac{2}{n}P(\backslash varphi\text{'}(k\text{'})\; =\; k\backslash mid\; \backslash varphi\text{'}(k)\; =\; k\text{'})\; =\; \backslash frac\; 2n$. Im anderen Fall, wo $kk$ durchmischen nicht zur ersten oder zweiten Karte wird, ist jeder andere Person, die nicht $kk$ oder $k^{\mathrm{\prime }}k\text{'}$ ist, als Wichtel gleich wahrscheinlich. Das sind noch $n-2n-2$ Personen. Diese müssen sich die Restwahrscheinlichkeit damit gleichmäßig aufteilen und wir erhalten $P({\phi }^{\mathrm{\prime }}(i)=k\mid {\phi }^{\mathrm{\prime }}(k)=k^{\mathrm{\prime }})=(1-\frac{2}{n})\cdot \frac{1}{n-2}=\frac{1}{n}P(\backslash varphi\text{'}(i)\; =\; k\; \backslash mid\; \backslash varphi\text{'}(k)\; =\; k\text{'})\; =\; (1-\backslash frac\; 2n)\; \backslash cdot\; \backslash frac\{1\}\{n-2\}\; =\; \backslash frac\; 1n$. Zusammengefasst hat ${\phi }^{\mathrm{\prime }}\backslash varphi\text{'}$ die Wahrscheinlichkeiten

Hier ist die Wahrscheinlichkeit, dass man der Co-Wichtel seines Co-Wichtels ist, mit $\frac{2}{n}\backslash frac\{2\}\{n\}$ zu hoch, und die Wahrscheinlichkeit, jemand anderes als Wichtel zu haben, mit $\frac{1}{n}\backslash frac\{1\}\{n\}$ zu gering. Für unsere Rechnung müssen wir auf ein Detail aufpassen: Sie funktioniert nur, wenn $n\ge 5n\; \backslash ge\; 5$.

Wir haben jetzt eine Permutation gefunden, bei der die Wahrscheinlichkeiten jeweils zu hoch und eine, wo sie jeweils zu niedrig sind. Können wir dies kombinieren, sodass die Wahrscheinlichkeiten passen?

Wir haben zwei Ausgangspermutationen $\sigma \backslash sigma$ und $\phi \backslash varphi$ gefunden. Bei einer ist die Wahrscheinlichkeit zu klein, dass man der Co-Wichtel seines Co-Wichtels ist, und bei der anderen zu groß. Um dieses Problem zu beheben, wollen wir beide Permutationen kombinieren, um die korrekten Wahrscheinlichkeiten zu erhalten. Wir wollen also mit einer gewissen, noch zu bestimmenden Wahrscheinlichkeit $pp$ die Konjugations-Methode mit $\sigma \backslash sigma$ anwenden und mit Wahrscheinlichkeit $1-p1-p$ die Konjugations-Methode mit $\phi \backslash varphi$ anwenden.

Wie müsste die Wahrscheinlichkeit $pp$ sein, damit die Wahrscheinlichkeit, der Co-Wichtel seines Co-Wichtels zu sein, genau $\frac{1}{n-1}\backslash frac\{1\}\{n-1\}$ ist? Bei $\sigma \backslash sigma$ ist die Wahrscheinlichkeit null und bei $\phi \backslash varphi$ ist die Wahrscheinlichkeit $\frac{2}{n}\backslash frac\; 2n$. Wir wollen also, dass $\frac{1}{n-1}=0\cdot p+(1-p)\cdot \frac{2}{n}\backslash frac\{1\}\{n-1\}\; =\; 0\backslash cdot\; p\; +\; (1-p)\backslash cdot\; \backslash frac\{2\}\{n\}$. Damit können wir $pp$ berechnen:

Das heißt, wir müssen mit der Wahrscheinlichkeit $\frac{n-2}{2n-2}\backslash frac\{n-2\}\{2n-2\}$ die Konjugations-Methode mit $\phi \backslash varphi$ anwenden und mit Wahrscheinlichkeit $\frac{n}{2n-2}\backslash frac\{n\}\{2n-2\}$ mit $\sigma \backslash sigma$.

Wenn unsere Methode funktioniert, müssen die anderen Wahrscheinlichkeiten ebenfalls passen: Bei $\sigma \backslash sigma$ ist die Wahrscheinlichkeit, dass eine Person einen selbst als Co-Wichtel hat, die nicht der Co-Wichtel von einem ist, genau $\frac{1}{n-2}\backslash frac\{1\}\{n-2\}$. Bei $\phi \backslash varphi$ ist diese Wahrscheinlichkeit $\frac{1}{n}\backslash frac\{1\}\{n\}$. Somit haben wir bei unserer Kombination die Wahrscheinlichkeit $p\cdot \frac{1}{n-2}+(1-p)\cdot \frac{1}{n}=\frac{1}{n-1}p\backslash cdot\; \backslash frac\{1\}\{n-2\}\; +\; (1-p)\backslash cdot\; \backslash frac\; 1n\; =\; \backslash frac\{1\}\{n-1\}$. Das heißt, diese Mischung liefert eine geheime Wichtelzuordnung.

Wenn bekannt ist, ob die Konjugations-Methode mit $\sigma \backslash sigma$ oder $\phi \backslash varphi$ durchgeführt wurde, haben wir nichts gewonnen, da das Mischen der beiden Permutationen gerade davon ausgeht, dass diese Information unbekannt ist. Wir müssen also eine Methode finden, wie wir die Konjugations-Methode mit $\sigma \backslash sigma$ oder $\phi \backslash varphi$ anwenden ohne zu wissen, ob wir sie mit $\sigma \backslash sigma$ oder $\phi \backslash varphi$ anwenden.

Wir haben schon einmal gesehen, wie wir eine Permutation zufällig ziehen können, ohne zu wissen, welche wir gezogen haben: Mit der Briefumschlag-Methode. Wir können also versuchen, unser Problem mit dieser zu lösen. Dafür benötigen wir genug Umschläge, damit das Wahrscheinlichkeitsverhältnis stimmt.

Damit dieses Verhältnis stimmt, müssen wir $nn$ Versionen von $\sigma \backslash sigma$ haben und $n-2n-2$ Versionen von $\phi \backslash varphi$. In den Umschlägen können aber nicht immer die gleichen Permutationen $\sigma \backslash sigma$ bzw. $\phi \backslash varphi$ liegen, da wir auf diese dann erst die Konjugations-Methode anwenden müssten und wir dafür die gezogene Permutation aufdecken müssten. Damit müssen die Permutationen, die wir in die Umschläge gesteckt haben, schon aus der Konjugations-Methode stammen.

Wir machen also folgendes:

1. Wir präparieren $nn$ Briefumschläge mit der Konjugations-Methode mit $\sigma \backslash sigma$ und $n-2n-2$ Briefumschläge mit der Konjugations-Methode mit $\phi \backslash 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.

Da diese Methode die Konjugations-Methode verbessert, werden wir sie die verbesserte Konjugations-Methode nennen.

Damit haben wir eine Methode gefunden, wie wir mathematisch korrekt wichteln können. Es stellt sich nur die Frage, wie viele Karten wir erstellen müssen: Wenn wir $2n-22n-2$ Briefumschläge erstellen müssen und jeder Umschlag $nn$ Karten enthält, müssen wir $n\cdot (2n-2)n\backslash cdot\; (2n-2)$ Karten erstellen und die Konjugations-Methode $2n-22n-2$ Mal anwenden. Dies werden ziemlich schnell ziemlich viele Karten:

Lohnt sich diese Methode trotzdem, bzw. können wir sie praktikabel machen?

Sehr viel Arbeit für eine Person

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

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

und

Konkret heißt das, wir mischen die Karten, schneiden sie auseinander, verschieben die Hälfte entsprechend der Permutation $\sigma \backslash sigma$ oder $\phi \backslash 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 \backslash sigma$ und einen mit der Permutation $\phi \backslash varphi$. Dann haben wir $nn$ Umschläge je Permutation $\sigma \backslash sigma$ und $\phi \backslash varphi$. Für das richtige Verhältnis brauchen wir aber $n-2n-2$ Umschläge mit $\phi \backslash varphi$, also müssen wir $22$ Umschläge mit der Permutation $\phi \backslash 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 \backslash sigma$ erstellen.

Dadurch muss, egal wie viele Leute mitwichteln, jede Person höchstens $22$ Umschläge anfertigen. Leider steigt die Anzahl der Karten, die jeder ausschneiden muss, mit $nn$. Also muss jeder $nn$ oder $2n2n$ 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 $nn$ 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 $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ 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 $nn$ 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 $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ durchmischt wird. Wir haben uns diese Methode für zwei fixpunktfreie Permutationen $\sigma \backslash sigma$ und $\phi \backslash 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}\backslash frac\{1\}\{n-1\}$ zu erreichen, muss man die beiden Permutationen kombinieren und mit der passenden Wahrscheinlichkeit entweder $\sigma \backslash sigma$ oder $\phi \backslash 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 $nn$ Briefumschläge mit der Konjugations-Methode mit $\sigma \backslash sigma$ und $n-2n-2$ Briefumschläge mit der Konjugations-Methode mit $\phi \backslash 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 $nn$ Mitspielern nur $2n-22n-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 \backslash sigma$ und einen mit $\phi \backslash 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!

Wir haben verschiedene Methoden kennengelernt, die man zum Wichteln mit $nn$ 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 $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ 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 $nn$ 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 $\{1,\dots ,n\}\backslash left\backslash \{1,\backslash ldots,n\backslash right\backslash \}$ durchmischt wird. Wir haben uns diese Methode für zwei fixpunktfreie Permutationen $\sigma \backslash sigma$ und $\phi \backslash 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}\backslash frac\{1\}\{n-1\}$ zu erreichen, muss man die beiden Permutationen kombinieren und mit der passenden Wahrscheinlichkeit entweder $\sigma \backslash sigma$ oder $\phi \backslash varphi$ beim Wichteln mit der Konjugations-Methode verwenden. Die Methode, die das garantiert, 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 $nn$ Briefumschläge mit der Konjugations-Methode mit $\sigma \backslash sigma$ und $n-2n-2$ Briefumschläge mit der Konjugations-Methode mit $\phi \backslash 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 $nn$ Mitspielern nur $2n-22n-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 \backslash sigma$ und einen mit $\phi \backslash varphi$) vorbereiten lässt.

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