Die Wochen vor Weihnachten sind die Zeit der Weihnachtsfeiern und Weihnachtsfeiern sind die Gelegenheit zum Wichteln. Für mich ein willkommener Anlass, darüber nachzudenken, wie wahrscheinlich es ist, dass das Wichteln in einer Wichtelcommunity schief läuft, d.h. - je nach Wichtelspielvariante - dass man sich selbst beschenken muss bzw. dass man das eigene Geschenk zieht. Inwiefern ist diese Wahrscheinlichkeit abhängig von der Teilnehmerzahl? Aus welchem Grund auch immer ich vernarrt bin in solche Denksportaufgaben, schlage ich mich gerne damit herum. Etwa wenn ich mitten in der Nacht aufwache und nicht mehr einschlafen kann.
Natürlich ist die Lösung des Problems ist relativ einfach googlebar (Wichteln ist ja ein wichtiges, allgemein bekanntes und sehr weit verbreitetes Thema), was für die meisten Probleme, mit denen ich mich sonst so rumschlage, leider nicht gilt. Mehr oder weniger zu Übungszwecken war es deshalb mein Ansporn, durch eigenständiges Nachdenken auf die Lösung zu kommen. Schnell merkte ich, dass das Problem nicht ganz elementar ist - zwischenzeitlich hatte ich drei verschiedene Lösungswege, die zu drei unterschiedlichen Ergebnissen führten. Es gelang mir dann doch, diese zu synthetisieren und als ich das kundtat, wurde ich aufgefordert, meine Denk- und Irrwege darzustellen, auf dass dies einen Einblick geben könnte, wie man sich mathematische Lösungen als Geisteswissenschaftler aus gefährlichem Halbwissen zusammenkonstruiert, hinterfragt und letztlich dabei doch irgendwie erfolgreich ist.
1. Bekanntes zusammenkramen: Kombinatorik
Wie fängt man so etwas an? Man trägt zusammen, was man denn so zum Thema weiß. Wie war das noch mit der Kombinatorik? Da gab es doch Unterschiede von wegen Berücksichtigung der Reihenfolge und dem Zurücklegen. Beim Wichteln (also Geschenke ziehen) ist die Reihenfolge relevant (wer bekommt welches Geschenk) und zurückgelegt wird nicht (jedes Geschenk wird nur einmal vergeben). Das heißt, man kann alle möglichen Wichtelnde-Wichtelgeschenk-Kombinationen über die Formel N!/(N-n)! berechnen. N ist dabei die Anzahl der Geschenke, n die Anzahl der Teilnehmer|innen (oder umgekehrt, es ist ja auch vollkommen gleich, da ja genau ein Geschenk auf eine|n Teilnehmer|in kommt. Jedenfalls wenn alle ein Geschenk mitbringen). Da N-n damit 0 und 0!=1 ist, bleiben N! mögliche Kombinationen von Geschenkreihenfolgen. Hilft einem das irgendwie bei der Frage, wie viele dieser Kombinationen gute (jede|r Teilnehmende hat ein Geschenk von jemand anderem) und wie viele schlechte Kombinationen (Mindestens ein|e Teilnehmende|r hat das eigene Geschenk gezogen) sind.
2. Bekanntes kombinieren: Mach dir ein Bild
In einem ersten Schritt habe ich nun tatsächlich die verschiedenen Kombinationen (die Permutationen genannt werden) aufgezeichnet und sie von Hand sortiert.
Mögliche Geschenkzuteilungen von 2 (links) und 3 (rechts) Mitwichtlern
Das Ergebnis sieht man in den Tabellen links: Großbuchstaben in der ersten Zeile stehen für Wichtel-Teilnehmende, die entsprechenden Kleinbuchstaben für deren Geschenke. Rot markiert sind Kombinationen, bei denen Teilnehmende eigene Geschenke erwichtelt haben (fortan Kollisionen genannt). Grün gefärbt sind die Reihen, die keine Kollisionen aufweisen, d.h. wo alle Teilnehmenden ein fremdes Geschenk erwichtelt haben. Im Fall von 2 Teilnehmenden (linke Tabelle) ist ist das in einem von zwei (also in der Häfte aller Fälle), bei drei Teilnehmenden in 2 von 6 möglichen Permutationen (also nur noch bei einem Drittel der Fälle) gegeben. Steigt also die Wahrscheinlichkeit der Kollisionen also mit steigender Teilnehmerzahl? Das hieße nichts gutes für unser Institutsweihnachtswichteln, wo sich 16 Mitspielende angekündigt hatten. Bevor ich mir aber die Mühe machte, Tabellen mit 16! (etwa 21 Billionen Zeilen) verschiedenen Kombinationen aufzumalen, suchte ich nach einem anderen Lösungsweg.
3. Holzwege abklappern: Der Baum der falschen Erkenntnis
Ein erweiterbarer Wahrscheinlichkeitsbaum: Bei 4 Mitspielern hat der erste eine Chance von 1/4, das eigene Geschenk zu erwichteln. Wenn danach noch jemand drankommt (in 3/4 aller Fälle), hat dieser 1/3 Chancen auf sein eigenes Geschenk, usw. Richtig?
Bei zwei Mitwichtlern gibt es genau zwei Möglichkeiten: Jeder bekommt das eigene Geschenk oder das des anderen. Also fifty-fifty. Kann man das nicht irgendwie auf drei Mitwichtelnde erweitern? Der erste hat eine Chance von 2/3, nicht das eigene Geschenk zu ziehen, in dem Fall liegt der zweite dann doch wieder 50/50.
Bei jedem weiteren Wichtler muss der Wahrscheinlichkeitsbaum nur nach vorne erweitert werden, so wie ich dies in der nebenstehenden Graphik versucht habe, abzubilden: Demnach müsste die Zahl der geglückten Runden bei 3 Mitwirkenden 2/3*1/2, also 1/3 betragen, bei 4 Mitwirkenden entsprechen 3/4*2/3*1/2, also 1/4 usw. betragen. Aber kann das stimmen? Das würde ja heißen, dass die Wahrscheinlichkeit für nicht geglückte Wichtelrunden umso unwahrscheinlicher wird, je mehr Leute mitwichteln. Bei unserer Institutsfeier wäre die Chance also gerade mal 1/16, läge also bei mageren 6,25%.
4. Halbwissen hinterfragen: Mal's noch einmal, Sam
Ich war jetzt doch soweit, den kombinatorischen Lösungsweg weiter zu verfolgen. 4!, also 24 mögliche Geschenkzuteilungskombinationen bekommt man ja noch auf ein DIN-A4- Blatt gemalt und, wie man links sieht, auch in einem Blogpost untergebracht. Jetzt nur noch die validen Kombinationen ermitteln und durchzählen - und merken, dass tatsächlich ein anderes Ergebnis als beim Wahrscheinlichkeitsbaum herauskommt: Offenbar gibt es nämlich nicht die von meiner Baumüberlegung vorhergesagten 6 von 24 Möglichkeiten (was 1/4 entsprechen würde), sondern ganze 9/24 (was 1,5/4 entspricht).
Da sich die Kombinatorik nur recht selten zu irren pflegt, musste also mein Wahrscheinlichkeitsbaum falsch sein. Aber warum? Und wie berechne ich die Wahrscheinlichkeit für mehr Teilnehmer? Weder meine Mathematik noch mein gesunder Baum-Entwurfs-Menschenverstand, noch meine DIN-A4-Blätter schienen auzureichen, um auf die richtige Lösung zu kommen. Den Gesichtsverlust durch Googlen wollte ich mir vorerst noch ersparen. Und was bleibt da? Ach, ich kann ja noch programmieren.
5. Der Rechner kann's zufällig: Millionenfaches Wichteln
Erster Programmieransatz war ein einfacher empirischer Test (auch Monte-Carlo-Methode genannt, danke an Till für den Hinweis). Ich brauche einfach eine Liste von Geschenken und lasse die Mitspielenden nacheinander ein Geschenk blind (über einen Zufallsgenerator) ziehen. Wenn jemand sein eigenes Geschenk zieht, ist die Runde gescheitert, wenn alle Geschenke gezogen wurden, ohne dass dies passierte, ist sie geglückt. Computer spielen schnell, es ist also kein Problem, 1 Millionen Runden oder mehr zu spielen (gut, wenn es tausende Mitspielende werden, muss man schon etwas warten, aber ich hatte ja nur 16). Außerdem kann man Ergebnisse für eine ganze Reihe unterschiedlicher Mitspielender ermitteln. Bei zweien glückt etwa jede zweite Runde, bei dreien etwa jede dritte - soweit gingen mein Baummodell und die Kombinatorik ja auch noch d'accord. Bei vier Mitspielenden liegt das Ergebnis um 0,375 herum, also so viel, wie meine Kombinationstabelle aussagte und 50% mehr, als der Wahrscheinlichkeitsbaum mich vermuten ließ.
Tatsächlich leuchtete mir dann ein, dass mein Baum zu simpel konstruiert war, da die Fälle für "nicht das eigene Geschenk" nicht hätten zusammengefasst werden dürfen. Wenn nämlich A das Geschenk von B zieht, und B ist danach an der Reihe, ist die Wahrscheinlichkeit für B genau Null, das eigene Geschenk zu ziehen. Der Wahrscheinlichkeitsbaum müsste also so viele Zweige haben, wie die Permutationstabelle Zeilen hat und wäre damit eben keine Vereinfachung mehr.
Die Permutationstabelle wird bei 5 und mehr Mitspielenden zu groß, mein vereinfachter Wahrscheinlichkeitsbaum ist unbrauchbar. Bleibt also vorerst nur die empirische Methode über Zufallsexperimente. Die liefert bei steigender Mitspielerzahl immer fast den gleichen Wert, der zwischen 3,6 und 3,7 liegt. Interessant, aber unbefriedigend, wenn man nicht genau versteht, weshalb das so ist.
6. Der Rechner kann's auch strukturiert: Spiel die Welt durch
Also noch einmal programmieren - statt einfach zufällig Geschenke zu ziehen, kann man auch einfach alle Permutationen von Geschenkabfolgen konstruieren, um sie hernach von den Mitspielern in immer der gleichen Reihenfolge ziehen zu lassen (oder umgekehrt, das ist völlig gleichgültig). Schließlich malt der Rechner nicht auf DIN-A4-Blätter und müsste auch mit mehr Tabellenzeilen zurecht kommen. Wobei N! natürlich trotzdem relativ schnell an Speicherplatz- und Prozessorgrenzen stößt.
Eine Liste in alle möglichen Permutationen zu überführen, ist eine sehr schöne Rekursionsaufgabe, die ich irgendwann einmal implementiert und wieder vergessen habe. Da ich dazu neige, viel Gehirnschmalz und Zeit bei solchen Aufgaben zu verlieren, habe ich mir dann doch eine Lösung von hier geklaut und auf meine Bedürfnisse angepasst. Jetzt konnte ich da drumrum ein Programm schreiben, welches alle Permutationen erzeugt und gegen die Mitwichtlerreihenfolge abprüft. Ergebnis: Je größer n, desto mehr nähert sich der Anteil der geglückten Wichtelrunden der Zahl 0,3678 an. Für n=10 dauert die Berechnung schon eine ganze Weile und ab n=11 gibt es einen OutOfMemory-Error, wenn man den Speicherplatz für die virtuelle Maschine nicht hochsetzt (ja, ich weiß, es ist nicht nötig, alle Permutationen zu speichern, an der Laufzeitproblematik ändert sich dadurch ja auch nichts).
Ausgabe meines maschinellen Wichtelprogramms. Links Anzahl der Teilnehmer, Mitte Ergebnis von 1 Mio Zufallsexperimenten, Rechts Ergebnis aller möglichen Permutationen.
Die sehr viel schnellere Zufallsgenerierungsmethode nähert sich bei größeren n auch immer mehr dieser Zahl an, so dass ich ihr vertraute, dass auch bei n=16 eine knapp 5/8 Wahrscheinlichkeit besteht, dass jemand von den 16 Mitwichtlern unserer Weihnachtsfeier das eigene Geschenk ziehen würde. Klar könnte man einfach die Runde wiederholen, aber da das Ganze anonym stattfinden sollte, wäre es schwierig gewesen mit dem Outing, das eigene Geschenk zu haben. Ich habe mir dann lieber eine 2-Gruppen-Lösung ausgedacht, wo man das Geschenk in die eine Wichtelgruppe gibt und eins aus der anderen Gruppe zieht. Klappt allerdings nur bei einer Mitspielerzahl, die nicht prim ist.
Über die richtige Lösung berichtete am Tag nach unserer Weihnachtsfeier auch DIE ZEIT Online und Post hoc ließ ich mich auch noch auf Google ein und fand diese diese nett gemachte Erläuterung. Mathematisch korrekt und ohne Umwege. Aber dass es eine solche gibt, hatte ich ja gar nicht in Abrede gestellt. Ich habe eigene Lösungswege gesucht, um meinen Denkapparat ein wenig zu ölen, damit er auch bei nicht-googlebaren Lösungen seinen Dienst tut. Ich habe dies hier aufgeschrieben, weil mein Kneipenlog-Kollege Dierk meinte, es würde vielleicht einen Einblick in (geistes)wissenschaftliche Prozesse geben.
[Code des Wichtelprogramms poste ich bei Interesse noch auf GitHub]
Quelle: http://texperimentales.hypotheses.org/1225
