The Nim-Sum of a Random Integer Partition

Stellen Sie sich ein Spiel vor, das mit Steinhaufen gespielt wird, bei dem zwei Spieler abwechselnd eine beliebige Anzahl von Steinen aus einem einzigen Haufen entfernen dürfen. Das Ziel ist es, der Letzte zu sein, der einen Zug ausführt, oder umgekehrt, den Gegner in eine Position zu bringen, in der er keinen gewinnenden Zug mehr hat. Dies ist das Spiel Nim, ein klassisches strategisches Rätsel, das seit über einem Jahrhundert untersucht wird. Das Geheimnis des Gewinnens liegt nicht im Zählen der Gesamtzahl der Steine, sondern in einer spezifischen Art, die Größen der Haufen unter Verwendung einer Regel zu kombinieren, die Addition und Subtraktion auf binärer Weise mischt. Wenn diese Kombination Null ergibt, ist der Spieler, der am Zug ist, dazu bestimmt zu verlieren, vorausgesetzt, sein Gegner spielt perfekt. Jahrzehntelang wussten Mathematiker, wie man diese Verlustpositionen für jede spezifische Anordnung von Haufen identifiziert. Doch eine tiefere, schwer fassbarere Frage blieb: Wenn man einfach eine feste Anzahl von Steinen sammelt und sie zufällig in Haufen aufteilt, wie oft ergibt eine solche zufällige Anordnung eine Verlustposition?

Diese Frage steht an der Schnittstelle zwischen Spieltheorie und der Untersuchung der Ganzzahlpartitionen, dem mathematischen Teilgebiet, das sich damit beschäftigt, wie eine Zahl in kleinere ganze Zahlen zerlegt werden kann. Während die Regeln für das Gewinnen eines einzelnen Spiels präzise und deterministisch sind, ist das Verhalten dieser Spiele, wenn die Ausgangsposition zufällig gewählt wird, überraschend komplex. Eine natürliche Frage ist, ob sich die Häufigkeit dieser Verlustpositionen, wenn die Gesamtzahl der Steine größer wird, in einem einfachen asymptotischen Muster einpendeln könnte. Doch die neue Arbeit von Daewon Kim von der University of Hawai'i at Mānoa zeigt, dass die Antwort weitaus komplexer ist als ein einfaches Einpendeln.

Kims Forschung konzentriert sich auf den speziellen Fall, in dem die Gesamtzahl der Steine gerade ist, da die Regeln des Spiels es unmöglich machen, dass eine ungerade Gesamtzahl jemals eine Verlustposition bildet. Die Studie untersucht, wie sich die Wahrscheinlichkeit einer Verlustposition verhält, wenn die Gesamtzahl der Steine zunimmt. Dabei zeigt sich ein faszinierendes Phänomen: Die tatsächliche Wahrscheinlichkeit, eine Verlustposition zu finden, schrumpft mit wachsender Steinzahl immer weiter gegen Null. Das bedeutet, dass Verlustpositionen im Verhältnis zu allen möglichen Anordnungen immer seltener werden. Was jedoch niemals zur Ruhe kommt, ist die normalisierte Dichte. Wenn man die Wahrscheinlichkeit um ihren natürlichen Basiswert skaliert, um die extremen Unterschiede auszugleichen, zeigt sich ein gezacktes, sich wiederholendes Sägezahnmuster. Dieser normalisierte Wert pendelt sich nicht auf einer stabilen Zahl ein, sondern schwankt unendlich zwischen dem Ein- und Zweifachen eines spezifischen Wertes.

Der Mechanismus, der dieses Verhalten antreibt, ist in der binären Natur der Gewinnregel des Spiels verwurzelt. Wenn eine große Zahl in kleinere Teile zerlegt wird, wirken die kleinsten Teile wie eine Quelle der Zufälligkeit, die die unteren Bits der Binärzahlen durchmischt. Die größten Teile sind so selten, dass sie das Ergebnis kaum beeinflussen. Es gibt jedoch einen spezifischen mittleren Bereich der Teilgrößen, der als kritischer Engpass fungiert. In diesem Bereich sind die Teile groß genug, um bedeutend zu sein, aber nicht so groß, dass sie verschwinden. Die Anzahl der Teile, die in diesen spezifischen Bereich fallen, beeinflusst das Ergebnis maßgeblich. Da sich dieser Bereich verschiebt, während die Gesamtzahl der Steine wächst, kippt das Gleichgewicht des Spiels vor und zurück. Das Muster zeigt markante Veränderungen immer dann, wenn die mit der Größe verbundene natürliche Skala eine Zweierpotenz überschreitet.

Um dies zu verstehen, könnte man den Prozess mit einer Uhr vergleichen, die sich jedes Mal zurücksetzt, wenn sie eine bestimmte Stunde erreicht, aber deren Zeiger sich mit einer Geschwindigkeit bewegt, die sich mit der Größe der Uhr selbst ändert. Während die Gesamtzahl der Steine zunimmt, bewegt sich der kritische Bereich der Teilgrößen nach oben. Die Parität, also ob die Anzahl der Teile in diesem Bereich gerade oder ungerade ist, fungiert als der entscheidende Treiber für diese Oszillation. Da die Verteilung der Teile einem statistischen Modell folgt, das einer Poisson-Verteilung ähnelt, schwankt die Chance, eine bestimmte Parität in diesem Bereich zu erreichen. Dieser Zyklus wiederholt sich unendlich oft, was bedeutet, dass der normalisierte Wert irgendwo zwischen dem Ein- und Zweifachen eines spezifischen Skalierungsfaktors liegen kann, je nachdem, wo man sich in diesem Zyklus befindet.

Die Studie geht auch über die Verlustpositionen hinaus. Sie zeigt, dass für jedes feste Zielergebnis der Nim-Sum die Dichte dieselbe primäre Abnahme aufweist und nach der gleichen Normalisierung demselben dyadischen Sägezahnmuster folgt. Egal, ob das Ziel darin besteht, dass die Haufen in diesem binären Sinne zu einer bestimmten, festen Zahl aufsummieren: Die Wahrscheinlichkeit, dieses Ziel zu erreichen, folgt diesem Muster. Dies deutet darauf hin, dass die binäre Struktur des Spiels eine permanente Signatur in der zufälligen Verteilung der Haufen hinterlässt, eine Signatur, die sich durch die schiere Größe der Zahlen nicht glätten lässt.

Um diese theoretischen Vorhersagen zu verifizieren, führte der Autor exakte Berechnungen für jede mögliche Anordnung von Steinen bis zu einer Gesamtzahl von zwanzigtausend durch. Anstatt Milliarden von Kombinationen einzeln aufzuzählen, nutzte die Studie einen anspruchsvollen computergestützten Ansatz, der das Problem als eine massive Zählaufgabe behandelte. Die Ergebnisse dieser exakten Berechnungen stimmten mit bemerkenswerter Präzision mit den theoretischen Vorhersagen überein und bestätigten, dass das Sägezahnmuster real ist und kein Artefakt des mathematischen Modells. Die Daten zeigten, dass die Wahrscheinlichkeit genau so ansteigt und abfällt, wie es die Theorie vorhersagte, wobei die Übergänge in genau den Momenten auftraten, in denen die natürliche Skala eine Zweierpotenz kreuzte.

Die Forschung untersucht auch die Natur des Übergangs zwischen diesen Spitzen und Tälern. Obwohl die Grafik wie scharfe, diskontinuierliche Sprünge aussieht, deutet die Analyse der endlichen Größen darauf hin, dass diese Sprünge über eine sehr kleine Skala geglättet werden. Diese Glättung wird durch dieselben statistischen Gesetze gesteuert, die die Parität von Zufallsereignissen beschreiben. Wenn die Gesamtzahl der Steine zunimmt, wird das Fenster, in dem diese Glättung stattfindet, immer schmaler, wodurch der scheinbare Sprung zu einer graduellen Verschiebung wird, die davon abhängt, ob die Anzahl der Teile im kritischen Bereich gerade oder ungerade ist.

Letztlich bietet diese Arbeit eine vollständige Beschreibung der Verteilung von Verlustpositionen im Spiel Nim, wenn die Ausgangskonfiguration zufällig gewählt wird. Sie löst eine lang gehegte Frage über die Häufigkeit dieser Positionen, indem sie zeigt, dass sie keinem einfachen, stetigen Trend folgen. Stattdessen werden sie durch ein komplexes Zusammenspiel zwischen der Größe der Haufen und der binären Struktur des Spiels gesteuert. Die Ergebnisse unterstreichen ein breiteres Prinzip in der Mathematik: Selbst in Systemen, die zufällig und glatt erscheinen, können tiefe arithmetische Strukturen beständige, scharfe Muster erzeugen, die einer Mittelwertbildung widerstehen. Die binäre Natur des Spiels stellt sicher, dass ein spezifischer Block an Information sichtbar und einflussreich bleibt, egal wie groß das System wird, und erzeugt einen Rhythmus, der sich unendlich wiederholt, während die Zahlen größer werden.