5Die Briefumschlag-Methode

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 $k$ nur seinen Co-Wichtel $\sigma\left(k\right)$ kennt und keine Information über seinen Wichtel $\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 $\left\{1,\ldots,n\right\}$ in eine Urne stecken, mischen, eine Permutation $\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 $k$ seinen Co-Wichtel $\sigma\left(k\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\colon\left\{1,\ldots,n\right\}\to\left\{1,\ldots,n\right\}$ können wir definieren oder aufschreiben, indem wir für jede Zahl $k\in\left\{1,\ldots,n\right\}$ angeben, was das zugehörige $\sigma\left(k\right)$ ist. Das geht zum Beispiel in Form einer Tabelle:

Zum Beispiel gehört zu der fixpunktfreien Permutation $\sigma\colon\{1{,}2,3\}\to\{1{,}2,3\}$ mit $\sigma(1)=2$, $\sigma(2)=3$ und $\sigma(3)=1$ die Tabelle

Auf diese Weise könnten wir jede der fixpunktfreien Permutationen von $\left\{1,\ldots,n\right\}$ auf einen Zettel schreiben und anschließend zufällig eine davon ziehen. Nun soll aber niemand die ganze gezogene Permutation $\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 $\{1{,}2,3\}$ gehörende Briefumschlag würde beispielsweise die drei Karten

enthalten.

Anschließend wird einer der Umschläge gezogen (also eine fixpunktfreie Permutation $\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,\ldots,n\}$, was das zugehörige $\sigma(k)$ ist. Das ist schon fast, was unser Ziel war: Nun müssen wir nur noch jeder Person ihre Nummer $k$ 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 $n$ Mitspieler folgendermaßen zusammenfassen:

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

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

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

   2. Für $k\in\left\{1,\ldots,n\right\}$ wird auf die untere Hälfte der mit $k$ beschrifteten Karte der Wert $\sigma\left(k\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$ Person“ erstellt, z.B. in Form einer Tabelle:

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

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

7. Jede Person schaut in der Tabelle nach, wer ihr Co-Wichtel ist: Person $k$ (deren Karte auf der oberen Hälfte mit $k$ beschriftet ist), schaut auf die untere Hälfte ihrer Karte, sieht dort die Zahl $\sigma\left(k\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 $n$ Mitspielern $d_n=n!\sum_{k=0}^n\frac{\left(-1\right)^k}{k!}$ fixpunktfreie Permutationen gibt. Für jede Permutation muss ein Umschlag vorbereitet werden, der jeweils $n$ beschriftete Karten enthält. Die Fakultät in der Formel deutet es schon an: Die Zahlen $d_n$ werden für wachsende Teilnehmerzahl $n\$sehr schnell sehr groß:

Schon bei sechs Mitspielern muss man somit $265$ Umschläge mit jeweils $6$ Karten vorbereiten und insgesamt $1590$ 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.