6Ändern der Fragestellung

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$ auf der Menge $\left\{1,\ldots,n\right\}$ der Teilnehmer generieren müssen. Dabei soll niemand sich selbst beschenken, also soll $\sigma$ fixpunktfrei sein. Und natürlich sollte die Methode jeder Person $k$ ihren Co-Wichtel $\sigma\left(k\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 $k$ weiß, dass ihr Co-Wichtel Person $k'$ ist, dann soll die Wahrscheinlichkeit, dass $k$ von irgendeinem ihrer $n-1$ Mitspieler beschenkt wird, für jeden Mitspieler $l$ gleich groß sein. Mathematisch ausgedrückt ist das eine bedingte Wahrscheinlichkeit: Gegeben $\sigma\left(k\right)=k'$ soll die Wahrscheinlichkeit für $\sigma\left(l\right)=k$ gleich $\frac{1}{n-1}$ für alle $l\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$. 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$ zufälliger machen?