7Die Konjugations-Methode

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

Die Permutation $\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 $k$ ihren Co-Wichtel $\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\}$ zunächst durchzumischen, also alle Teilnehmer auf zufällige Art und Weise „umzubenennen“, indem wir ihnen neue Zahlen $\left\{1,\ldots,n\right\}$ zuweisen. Dann wenden wir $\sigma$ auf diese neue Reihenfolge an.

Weil $\sigma$ bekannt ist, kann man zwar immer noch $\sigma^{-1}$ berechnen, aber man weiß nicht mehr, zu welcher Person die Zahl $\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$ 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$ 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\}$ 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, 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, n$ er selbst ist und welche Zahl $1, \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.