Additive Subtraction Games

Diese Arbeit liefert den ersten vollständigen Beweis für die geschlossene Formel zur Bestimmung der P-Positionen in additiven Subtraktionsspielen im primitiv-quadratischen Regime und zeigt, dass die Nim-Wert-Folgen auf linearen Verschiebungen dieser Positionen basieren.

Das Wesentliche

Stellen Sie sich vor, Sie spielen ein Spiel mit zwei Freunden. Vor Ihnen liegen Haufen von Steinen. Ihr Ziel ist es, den letzten Stein zu nehmen. Aber es gibt eine Regel: Sie dürfen nur eine bestimmte Anzahl von Steinen auf einmal wegnehmen. Diese erlaubten Mengen sind festgelegt, sagen wir: 3, 5 oder 8 Steine.

Das ist ein klassisches „Subtraktionsspiel". Die große Frage für Mathematiker ist: Wer gewinnt? Wenn Sie am Zug sind, können Sie den Haufen so verkleinern, dass Ihr Gegner in einer verlorenen Position landet? Oder sind Sie selbst schon verloren, egal was Sie tun?

In diesem Papier lösen die Autoren Urban Larsson und Hikaru Manabe ein sehr spezifisches, aber schwieriges Rätsel aus diesem Spiel. Hier ist die Erklärung in einfachen Worten, mit ein paar Bildern aus dem Alltag.

1. Das Spiel und die „versteckten" Regeln

Stellen Sie sich den Haufen als eine lange Straße vor, auf der die Steine liegen. Jeder Stein hat eine Nummer (0, 1, 2, 3...).

• P-Positionen (Die „Sicheren Häfen"): Das sind die Nummern, auf denen Sie stehen wollen, wenn Sie am Zug sind. Wenn Sie hier stehen, haben Sie eine Strategie, die garantiert, dass Sie gewinnen (vorausgesetzt, Sie spielen perfekt). In der Sprache der Mathematik ist der Wert dieser Position „0".
• N-Positionen (Die „Gefahrenzonen"): Hier stehen Sie, wenn Sie verlieren werden, wenn der Gegner perfekt spielt.

Das Problem: Bei einfachen Regeln (z. B. man darf nur 1 oder 2 Steine nehmen) ist das Muster leicht zu erkennen. Aber bei komplexeren Regeln, wie in diesem Papier untersucht, wird es chaotisch. Die Autoren schauen sich einen speziellen Fall an, bei dem die erlaubten Züge aus drei Zahlen bestehen: $a$, $b$ und $a+b$.

2. Der „Ziegelstein"-Bau

Die Autoren haben eine Formel gefunden, die wie ein Baukasten funktioniert.
Stellen Sie sich vor, Sie bauen eine Mauer aus Ziegelsteinen. Die Formel sagt Ihnen genau, an welcher Stelle der Straße Sie einen „Sicheren Hafen" (eine P-Position) platzieren müssen.

Die Formel sieht kompliziert aus, aber das Prinzip ist einfach:
Sie nehmen eine Zahl $n$ (die Nummer des Steins), fügen etwas hinzu, das davon abhängt, wie oft $n$ durch $a$ teilbar ist, und noch etwas, das davon abhängt, wie oft $n$ durch eine andere Zahl $\delta$ teilbar ist.

Das Ergebnis ist eine Liste von Zahlen: $w_0, w_1, w_2, \dots$. Diese Zahlen sind die „Sicheren Häfen".

• Das Rätsel: Niemand hatte bisher bewiesen, dass diese Formel wirklich immer funktioniert. Es war wie ein Rezept, das jeder benutzt hat, aber niemand wusste, warum es schmeckt. Die Autoren haben nun den „Koch" (den Beweis) geliefert.

3. Die vier Farben der Welt

Das Spannendste an diesem Spiel ist, dass es nicht nur „Gewinnen" und „Verlieren" gibt. Es gibt vier verschiedene Arten von Positionen, die wie vier Farben in einem Mosaik das ganze Spielfeld bedecken:

1. Grün (Wert 0): Die „Sicheren Häfen" (P-Positionen). Hier stehen Sie sicher.
2. Rot (Wert 1): Wenn Sie hier stehen, können Sie mit einem Zug (nämlich $a$ Steine wegnehmen) direkt auf einen „Grünen" Stein springen.
3. Blau (Wert 2): Hier können Sie mit einem Zug (nämlich $b$ Steine wegnehmen) auf einen „Grünen" Stein springen.
4. Gelb (Wert 3): Hier können Sie auf einen „Roten" Stein springen, aber nicht direkt auf einen Grünen.

Die Autoren zeigen, dass diese vier Farben das ganze Universum der Spielpositionen lückenlos abdecken. Es gibt keine Position, die keine Farbe hat, und keine Position, die zwei Farben gleichzeitig hat.

4. Der Tanz der Abstände (Die „Lücken")

Wie verteilen sich diese Farben?
Stellen Sie sich vor, Sie gehen die Straße entlang und zählen die Schritte zwischen den „Grünen" Häfen.

• Manchmal ist der Abstand klein (nur 1 Schritt).
• Manchmal ist er mittelgroß.
• Manchmal ist er groß.

Die Autoren haben entdeckt, dass diese Abstände nicht zufällig sind. Sie folgen einem strengen Rhythmus, der von zwei Zahlen ($a$ und $\delta$) bestimmt wird.
Es ist wie ein Tanz:

• Wenn Sie einen bestimmten Schritt machen (eine „Lücke" der Größe $a+1$), dann gibt es immer eine bestimmte Anzahl von kleinen Schritten (Größe 1) davor und danach.
• Die Autoren haben berechnet, wie oft diese speziellen „Tanzschritte" vorkommen, die eine Kollision erzeugen (also wo sich die Muster überlappen).

5. Warum ist das wichtig?

Bisher war dieses Rätsel ein offenes Geheimnis aus dem berühmten Buch Winning Ways (ein Art „Bibel" für Strategiespiele) aus dem Jahr 1982. Die Formel war da, aber der Beweis fehlte.
Die Autoren haben nun:

1. Den Beweis geliefert, dass die Formel stimmt.
2. Gezeigt, wie man alle vier Spielwerte (0, 1, 2, 3) exakt berechnet.
3. Erklärt, warum dieses spezielle Szenario („primitive quadratische Phase") das Herzstück der Komplexität ist.

Zusammenfassend:
Die Autoren haben ein mathematisches Puzzle gelöst, das seit 40 Jahren offen war. Sie haben gezeigt, dass hinter dem scheinbar chaotischen Spiel mit den Steinen eine wunderschöne, regelmäßige Struktur steckt, die sich wie ein gut choreografierter Tanz verhält. Sie haben nicht nur die „Sicheren Häfen" gefunden, sondern auch genau erklärt, wie man von jedem anderen Punkt aus dorthin gelangt.

Für jeden, der gerne Strategien spielt oder die verborgene Ordnung in scheinbar zufälligen Dingen sucht, ist das ein faszinierender Einblick in die Welt der Mathematik.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des Papers „Additive Subtraction Games" von Urban Larsson und Hikaru Manabe auf Deutsch.

1. Problemstellung und Kontext

Das Paper untersucht additive Subtraktionsspiele (Subtraction Games), eine Klasse von Zwei-Personen-Spielen, die auf einem Haufen von Spielsteinen gespielt werden. Spieler entfernen abwechselnd eine Anzahl $s$ von Steinen, wobei $s$ aus einer festen Menge $S$ positiver ganzer Zahlen stammen muss. Ein Spieler, der keinen gültigen Zug machen kann (da jede Subtraktion zu einer negativen Zahl führen würde), verliert.

Der Fokus liegt auf der Bestimmung der Nim-Werte (auch Nimbers genannt) für die Menge $S = \{a, b, a+b\}$, wobei $b = a + \delta$. Die Autoren konzentrieren sich auf den sogenannten primitiven quadratischen Regime, definiert durch die Bedingungen:
$$a < \delta < 2a \quad \text{und} \quad \gcd(a, \delta) = 1.$$

Dieser Regime ist von besonderem Interesse, da er die erste Parameterbereich darstellt, in dem die beiden Skalen $a$ und $\delta$ nicht-trivial in der zugrunde liegenden mathematischen Struktur interagieren. Das Problem wurde bereits 1982 in „Winning Ways" von Berlekamp et al. erwähnt, wo eine geschlossene Formel für die $P$-Positionen (Positionen mit dem Nim-Wert 0) vorgeschlagen wurde. Diese Formel basiert auf Beatty-artigen Ausdrücken mit rationalen Moduln. Bis vor kurzem fehlte jedoch ein vollständiger Beweis für diese Behauptung in der Literatur. Miklós und Post (2024) hatten zwar die Periodizität des Ergebnisses bewiesen, aber nicht die explizite geschlossene Formel verwendet.

2. Methodik

Die Autoren verwenden eine Kombination aus kombinatorischer Spieltheorie und elementarer Zahlentheorie, um die Struktur der Nim-Werte vollständig zu charakterisieren.

• Induktionsbeweis: Die Hauptstrategie ist ein starker Induktionsbeweis über die Größe der Positionen. Unter der Annahme, dass die Nim-Werte für alle Positionen kleiner als $x$ korrekt zugeordnet sind, wird die Konsistenz der „mex-Regel" (Minimum Excluded Value) an der Position $x$ überprüft.
• Anti-Kollision und Erreichbarkeit: Für jede Kandidatenmenge von Positionen muss gezeigt werden:
  1. Anti-Kollision: Kein Zug führt von einer Position in der Menge zu einer anderen Position in derselben Menge.
  2. Erreichbarkeit: Von jeder Position in der Menge kann man zu Positionen mit allen kleineren Nim-Werten gelangen.
• Zahlentheoretische Analyse der Lücken: Ein zentraler Teil der Arbeit ist die Analyse der Lückenstruktur (Gap Structure) der Folge der $P$-Positionen. Die Autoren definieren eine Folge $w_n$ und analysieren die Differenzen $g_n = w_{n+1} - w_n$. Sie zeigen, dass diese Lücken nur vier mögliche Werte annehmen und periodisch sind.
• Kollisionszählung (Collision Counting): Um die Partitionierung der natürlichen Zahlen zu beweisen, untersuchen sie die Schnittmenge der Menge der $P$-Positionen $W_0$ mit ihrer Verschiebung $W_0 - \delta$. Die Anzahl der „Kollisionen" (d.h. Paare $(m, n)$ mit $w_n - w_m = \delta$) wird durch eine detaillierte Analyse von „Kollisionsfenstern" bestimmt, die auf den Restklassen modulo $a$ und $\delta$ basieren.

3. Schlüsselbeiträge und Ergebnisse

Das Hauptergebnis ist die vollständige Bestimmung der Nim-Wert-Struktur für den primitiven quadratischen Regime.

A. Die geschlossene Formel für $P$-Positionen

Die Autoren bestätigen die in „Winning Ways" vermutete Formel für die Menge der $P$-Positionen ($W_0$, Nim-Wert 0). Für $n \in \mathbb{N}_0$ ist:
$$w_n := n + a \left\lfloor \frac{n}{a} \right\rfloor + b \left\lfloor \frac{n}{\delta} \right\rfloor$$
wobei $b = a + \delta$.
$W_0 = \{w_n : n \ge 0\}$.

B. Partitionierung der natürlichen Zahlen

Der Hauptbeweis (Satz 1) zeigt, dass die natürlichen Zahlen $\mathbb{N}_0$ durch vier disjunkte Mengen partitioniert werden, die jeweils einem Nim-Wert entsprechen:

1. Nim-Wert 0: $W_0$ (die $P$-Positionen).
2. Nim-Wert 1: $W_1 = W_0 + a$.
3. Nim-Wert 2: $W_2 = W_0 - b$.
4. Nim-Wert 3: $W_3 = (W_0 - \delta) \setminus W_0$.

Es wird bewiesen, dass diese vier Mengen eine Partition von $\mathbb{N}_0$ bilden.

C. Der Kollisionszählungssatz (Theorem 7)

Ein entscheidendes technisches Ergebnis ist die Zählung der Kollisionen in einem Periode. Für die Menge $C = (W_0 - \delta) \cap W_0$ (Positionen, die sowohl in $W_0$ als auch in $W_0 - \delta$ liegen) gilt innerhalb einer Periode der Länge $(3\delta + a)a$:
$$|C|_p = a \cdot d$$
wobei $d = \delta - a$.
Dieses Ergebnis wird durch eine feine Analyse der Restklassen von $n$ modulo $\delta$ hergeleitet. Die Autoren identifizieren drei Regionen für die Restklassen $r$ (links-restringiert, unbeschränkt, rechts-restringiert), die bestimmen, wie viele Kollisionsfenster zu einem bestimmten Lückentyp beitragen. Die Summe dieser Beiträge ergibt exakt $ad$.

D. Periodizität

Die Autoren bestätigen, dass die Index-Periode $a\delta$ beträgt, während die Heap-Periode (die tatsächliche Länge des Zahlenintervalls) $(3\delta + a)a$ ist.

4. Bedeutung und Implikationen

• Lösung eines offenen Problems: Das Paper liefert den ersten vollständigen Beweis für die geschlossene Formel der $P$-Positionen in diesem spezifischen Regime, die seit 1982 vermutet, aber nicht bewiesen war.
• Strukturkomplexität: Es wird gezeigt, dass der primitive quadratische Regime ($a < \delta < 2a$) die Quelle der quadratischen Komplexität des Problems darstellt. Außerhalb dieses Bereichs reduziert sich das Problem entweder auf lineare Komplexität oder behält die quadratische Struktur bei, ohne neue Phänomene zu erzeugen.
• Verbindung zur Zahlentheorie: Die Arbeit verbindet kombinatorische Spieltheorie eng mit der Theorie der Beatty-Folgen und Brackets-Ausdrücken. Sie zeigt, dass die Nim-Werte affine Verschiebungen einer einzigen, durch Floor-Funktionen definierten Folge sind.
• Erweiterbarkeit: Die Methoden, insbesondere die Analyse der Kollisionsfenster und der Restklassenverteilung, bieten einen neuen Ansatz für die Untersuchung anderer additiver Subtraktionsspiele und verwandter zahlentheoretischer Probleme (z. B. die Struktur von Kollisionsmengen bei anderen Verschiebungen $k$).

Zusammenfassend stellt dieses Paper eine tiefgehende mathematische Charakterisierung eines klassischen Spiels dar, indem es eine elegante, geschlossene Formel mit einem rigorosen Beweis der vollständigen Nim-Wert-Struktur verbindet und dabei neue zahlentheoretische Techniken zur Analyse von Lückenmustern entwickelt.