3Mathematische Beschreibung des Wichtelns

Wir müssen erstmal die Gruppe von Teilnehmern mathematisch repräsentieren. Nehmen wir an, dass beim Wichteln $n$ Personen mitmachen wollen, wobei $n$ eine beliebige natürliche Zahl (und am besten größer als $1$) ist. Dann können wir jeder Person eine Zahl zwischen $1$ und $n$ zuweisen und die gesamte Gruppe als die Menge $\ \left\{1,\ldots,n\right\}$ beschreiben. (Natürlich könnte man die Teilnehmer-Gruppe auch durch jede andere $n$-elementige Menge beschreiben, jedoch ist $\left\{1,\ldots,n\right\}$ 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\ \left\{1,\ldots,n\right\}$ eine Person $k'\ \in\ \left\{1,\ldots,n\right\}$ zuordnen, der sie etwas schenken soll. Dann ist $k'$ der Co-Wichtel von $k$. Diese Zuordnung ist nichts anderes als eine Funktion von der Menge $\ \left\{1,\ldots,n\right\}$ in sich selbst. Wir symbolisieren sie mit dem Buchstaben $\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'\ \in\ \left\{1,\ldots,n\right\}$ soll es ein $k\ \in\ \left\{1,\ldots,n\right\}$ geben mit $\sigma\left(k\right)\ =\ k'$. 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\ \left\{1,\ldots,n\right\}$ soll $\sigma\left(k\right)\ \ne k\$ gelten. Eine Funktion mit dieser Eigenschaft heißt fixpunktfrei.

Eine surjektive Funktion $\sigma\colon\left\{1,\ldots,n\right\}\to\left\{1,\ldots,n\right\}$ zwischen endlichen Mengen mit gleich vielen Elementen hat automatisch auch die Eigenschaft, dass kein $k'\ \in\ \left\{1,\ldots,n\right\}$ mehr als einmal von $\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 $\left\{1,\ldots,n\right\}$ einen speziellen Namen.

Fassen wir zusammen: Wir haben die Gruppe von Teilnehmern durch die Menge mit den Elementen $1$ bis $n$ 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$ auf $\left\{1,\ldots,n\right\}$ wählen und diese zum Wichteln benutzen. Dafür würden wir festlegen, dass jede Person $k\in\left\{1,\ldots,n\right\}$ der Person $\sigma\left(k\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.