🔢 mathematics

The Ordered Zeckendorf Game

Diese Arbeit stellt das „geordnete Zeckendorf-Spiel" vor, eine neuartige kombinatorische Zweipersonen-Variante, die durch die Einschränkung auf aufeinanderfolgende Summanden und eine Umsortier-Option eine ausgeglichenere strategische Dynamik erzeugt, bei der Spieler 1 für fast alle $n \leq 25$ gewinnt, während gleichzeitig die Endlichkeit des Spiels bewiesen und die Spielkomplexität von linearer bis quadratischer Länge analysiert wird.

Ursprüngliche Autoren: Ivan Bortnovskyi, Michael Lucas, Steven J. Miller, Iana Vranesko, Ren Watson, Cameron White

Veröffentlicht 2026-03-31

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ivan Bortnovskyi, Michael Lucas, Steven J. Miller, Iana Vranesko, Ren Watson, Cameron White

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stell dir vor, du hast einen Haufen kleiner Steine, und dein Ziel ist es, sie in eine ganz bestimmte, perfekte Anordnung zu bringen. Das ist im Grunde das Herzstück dieses wissenschaftlichen Artikels über das „Geordnete Zeckendorf-Spiel".

Hier ist eine einfache Erklärung, wie das Spiel funktioniert, warum es spannend ist und was die Forscher herausgefunden haben – ganz ohne komplizierte Formeln.

1. Das Grundspiel: Ein Haufen Steine, eine magische Regel

Stell dir vor, du beginnst mit n kleinen Steinen (die alle den Wert „1" haben).
Das Ziel ist es, diese Steine so umzuordnen, dass sie den Zeckendorf-Satz erfüllen. Das ist eine mathematische Regel, die besagt: Jede Zahl kann als Summe von bestimmten „Fibonacci-Steinen" (1, 2, 3, 5, 8, 13...) dargestellt werden, aber niemals zwei aufeinanderfolgende Fibonacci-Zahlen dürfen nebeneinander stehen.

Das alte Spiel (Ungeordnet): In der klassischen Version durften die Spieler jeden Stein mit jedem anderen kombinieren, egal wo er lag. Es war wie ein Haufen Kugeln, die man in einen Topf wirft. Die Forscher wussten schon lange: Wenn man gut spielt, gewinnt immer der zweite Spieler. Das war etwas langweilig, weil der erste Spieler keine Chance hatte.
Das neue Spiel (Geordnet): Hier kommt der Twist! Die Steine liegen in einer Reihe (wie Perlen auf einer Schnur). Du darfst nur mit Nachbarn interagieren.
- Zusammenfügen: Wenn zwei Nachbarn passen (z. B. eine 3 und eine 5), kannst du sie zu einer 8 verschmelzen.
- Teilen: Du kannst eine große Zahl auch wieder in zwei kleinere Nachbarn aufspalten.
- Der neue Trick – Der „Switch": Das ist der wichtigste Unterschied! Du darfst zwei benachbarte Steine tauschen, wenn sie in der falschen Reihenfolge liegen (z. B. eine 8 vor einer 3). Das erlaubt es dir, die Reihe neu zu sortieren, um neue Kombinationen zu ermöglichen.

2. Warum ist das Spiel so spannend?

Stell dir das Spiel wie ein Puzzle vor, bei dem du nicht nur die Teile zusammensetzen musst, sondern sie auch erst in die richtige Reihenfolge bringen musst, bevor du sie verbinden kannst.

Die Überraschung: Im alten Spiel war das Ergebnis vorhersehbar (Spieler 2 gewinnt immer). Im neuen, geordneten Spiel ist es ein echter Kampf. Die Forscher haben herausgefunden, dass bei den meisten Zahlen (bis 25) Spieler 1 gewinnt. Nur bei der Zahl 18 hat Spieler 2 eine Chance. Das bedeutet: Durch die Regel „nur Nachbarn" und den „Tausch-Trick" ist das Spiel viel ausgeglichener und strategischer geworden. Es ist wie der Unterschied zwischen einem zufälligen Wurf und einem Schachspiel, bei dem die Position jedes Bauern zählt.

3. Die großen Fragen: Wie lange dauert das Spiel?

Die Forscher haben sich zwei extreme Fragen gestellt:

Wie schnell kann man gewinnen? (Der „Sprint")
Wenn beide Spieler versuchen, so schnell wie möglich zu gewinnen, ist die kürzeste Zeit genau die Anzahl der Steine minus die Anzahl der Steine im Endergebnis. Das ist wie ein Marathon, bei dem man den direkten Weg nimmt.
Wie lange kann man das Spiel hinauszögern? (Der „Marathon")
Was, wenn beide Spieler versuchen, das Spiel so lange wie möglich zu machen? Die Forscher haben bewiesen, dass das Spiel immer endet (es gibt kein unendliches Hin und Her). Aber wie lange kann es dauern?
- Die Antwort ist: Es wächst quadratisch. Das bedeutet, wenn du die Anzahl der Startsteine verdoppelst, vervierfacht sich die maximale Spielzeit fast.
- Sie haben eine Strategie gefunden („Long Game Strategy"), die das Spiel extrem lang macht: Man tauscht viel, spaltet Steine auf und fügt sie wieder zusammen, um die Reihen immer wieder neu zu ordnen, bevor man endlich zum Ziel kommt.

4. Zufall und Wahrscheinlichkeit

Die Forscher haben auch simuliert, was passiert, wenn Spieler ihre Züge zufällig wählen (wie beim Würfeln).

Das Ergebnis: Die Länge der Spiele folgt einer ganz bestimmten Kurve, die man „Log-Normal-Verteilung" nennt.
Eine Analogie: Stell dir vor, du wirfst Tausende von Bällen von einer Klippe. Die meisten landen in der Nähe, aber einige fliegen sehr weit. Die Verteilung der Landepunkte sieht nicht wie eine Glocke aus, sondern eher wie eine schräge Kurve, die lange nach rechts ausläuft. Das bedeutet: Die meisten Spiele dauern eine mittlere Zeit, aber es gibt einige sehr lange „Ausreißer", die das Spiel extrem in die Länge ziehen.

5. Was bedeutet das für die Zukunft?

Dieses Spiel ist mehr als nur ein Zeitvertreib. Es ist ein Labor für Mathematiker und Informatiker.

Es zeigt, wie kleine Regeln (wie „nur Nachbarn" oder „Tauschen") die gesamte Dynamik eines Systems verändern können.
Es wirft neue Fragen auf: Gibt es eine perfekte Strategie für jede Zahl? Wie verhält sich das Spiel, wenn man mehr als zwei Spieler hat?
Die Forscher hoffen, dass die Erkenntnisse helfen, andere komplexe Systeme zu verstehen, von der Verschlüsselung von Daten bis hin zur Analyse von Netzwerken.

Zusammenfassend:
Die Autoren haben ein altes mathematisches Rätsel neu erfunden, indem sie es in eine Reihe gezwungen haben. Das Ergebnis ist ein Spiel, das weniger vorhersehbar, strategisch tiefer und mathematisch reicher ist als das Original. Es ist wie der Unterschied zwischen einem Haufen loser Puzzleteile und einem Puzzle, bei dem du die Teile erst sortieren musst, bevor du sie einfügen kannst – und dabei darfst du sie sogar tauschen, um den perfekten Weg zu finden.

1. Problemstellung und Motivation

Das Paper führt eine neue Variante des klassischen Zeckendorf-Spiels ein, das auf dem Zeckendorf-Theorem basiert. Dieses Theorem besagt, dass jede positive ganze Zahl $n$ eindeutig als Summe nicht-konsecutiver Fibonacci-Zahlen dargestellt werden kann (wobei $F_1=1, F_2=2$ ).

Im klassischen Spiel (von Baird-Smith et al.) arbeiten die Spieler mit einer ungeordneten Multimenge von Fibonacci-Zahlen. Es ist bekannt, dass in dieser Variante Spieler 2 für alle $n > 2$ eine dominante Gewinnstrategie besitzt, was die strategische Komplexität des Spiels stark einschränkt.

Die Autoren modifizieren das Spiel, indem sie eine Ordnungsbeschränkung einführen:

Der Startzustand ist eine geordnete Liste (Tupel) von $n$ Einsen ( $F_1$ ).
Alle erlaubten Züge (Mergen, Splitting, Switching) müssen benachbarte Elemente betreffen.
Eine neue Zugart, das Switching (Tauschen benachbarter Elemente $F_i, F_j$ mit $i > j$ ), wird eingeführt, um die Reihenfolge wiederherzustellen und weitere Operationen zu ermöglichen.

Das Ziel ist es, die dynamischen und strategischen Eigenschaften dieses geordneten Spiels zu analysieren und zu untersuchen, wie die Einführung von Ordnung und Nachbarschaftsbeschränkungen das Spielverhalten im Vergleich zur ungeordneten Version verändert.

2. Methodik

Die Analyse kombiniert theoretische Beweise mit computergestützten Simulationen:

Monovariante (Monovariante): Um die Terminierung des Spiels und den Endzustand zu beweisen, definieren die Autoren eine streng fallende Monovariante $f(S)$ . Für einen Zustand $S = (F_{i_1}, \dots, F_{i_k})$ ist diese definiert als:
$f(S) = \sum_{j=1}^{k} (k + 1 - j) F_{i_j}$
Diese Funktion kombiniert die Summe der Fibonacci-Indizes mit ihrer Position im Tupel. Jeder legale Zug (Mergen, Splitting, Switching) reduziert den Wert von $f(S)$ strikt, was Zyklen ausschließt und die Konvergenz garantiert.
Zustandsübergangsgraphen: Zur Analyse der maximalen Spiellänge werden Zustandsdiagramme verwendet, die die Wiederholungen höherer Fibonacci-Terme ( $F_i$ für $i \ge 3$ ) unter einer spezifischen Strategie (Long Game Strategy, LGS) modellieren.
Algorithmische Simulationen: Um Gewinnstrategien und Verteilungen der Spiellängen zu untersuchen, wurden umfangreiche Simulationen (z. B. 10.000 Spiele für $n=150$ ) in Python und C++ durchgeführt. Dabei wurden sowohl deterministische Strategien als auch zufällige Züge analysiert.

3. Wichtige Beiträge und Ergebnisse

A. Terminierung und Endzustand (Theorem 1.3)

Das Spiel terminiert immer in endlich vielen Zügen.
Der Endzustand ist exakt die Zeckendorf-Zerlegung von $n$ , dargestellt als eine streng aufsteigende Folge von Fibonacci-Zahlen.
Dies wird durch die Monovariante bewiesen, die sicherstellt, dass das Spiel nicht in einem Zyklus stecken bleibt und nur die eindeutige Zerlegung als Endzustand zulässt, da alle anderen Darstellungen weitere Züge ermöglichen.

B. Spiellänge: Untere und obere Schranken

Die Autoren untersuchen die minimale und maximale Anzahl an Zügen, um den Endzustand zu erreichen.

Minimale Länge (Proposition 1.4): Die kürzestmögliche Spiellänge beträgt genau $n - Z(n)$ , wobei $Z(n)$ die Anzahl der Terme in der Zeckendorf-Zerlegung von $n$ ist. Dies entspricht einer gierigen Strategie (Greedy-Algorithmus), bei der benachbarte Paare so schnell wie möglich gemergt werden.
Maximale Länge (Theorem 1.5 & 1.11):
- Eine obere Schranke wurde mit $M(n) \le \frac{n(n-1)}{2}$ etabliert.
- Durch eine verfeinerte Analyse unter Berücksichtigung der Manipulation von „Steinen" (Fibonacci-Einheiten) wurde eine präzisere obere Schranke abgeleitet:
  $M(n) \le \frac{n^2}{2} - \frac{1}{32} n \log_\phi n + o(n \log_\phi n)$
- Eine untere Schranke wurde durch die „Long Game Strategy" (LGS) bewiesen, die Züge priorisiert (Switching, dann Mergen von Einsen, dann Splitting von rechts, dann Mergen von links).
- Asymptotisches Verhalten (Korollar 1.12): Die maximale Spiellänge wächst quadratisch:
  $M(n) = \frac{n^2}{2} - \Theta(n \log_\phi n)$
  wobei $\phi$ der goldene Schnitt ist.

C. Gewinnstrategien und Spielverlauf

Ausgewogenheit: Im Gegensatz zum klassischen Spiel (wo Spieler 2 dominiert), zeigt das geordnete Spiel ein viel ausgewogeneres Bild.
Ergebnisse für kleine $n$ : Empirische Simulationen zeigen, dass Spieler 1 für fast alle Werte $n \le 25$ eine Gewinnstrategie hat. Die einzige Ausnahme im untersuchten Bereich ist $n = 18$ , wo Spieler 2 gewinnen kann.
Offenes Problem: Eine allgemeine Gewinnstrategie für $n > 25$ konnte aufgrund der kombinatorischen Explosion des Spielbaums nicht vollständig gelöst werden. Die Existenz einer allgemeinen Strategie für einen der Spieler bleibt offen.

D. Probabilistische Analyse

Bei zufälligen Spielen (jeder legale Zug gleich wahrscheinlich) konvergiert die Verteilung der Spiellängen für große $n$ gegen eine Log-Normal-Verteilung (Conjecture 3.2).
Die Simulationen deuten darauf hin, dass bei zufälligen Zügen beide Spieler mit gleicher Wahrscheinlichkeit gewinnen, was auf eine Symmetrie in den dynamischen Eigenschaften hindeutet.

4. Bedeutung und Ausblick

Das Paper erweitert das Feld der zahlentheoretischen Spiele erheblich:

Strategische Tiefe: Die Einführung der Ordnungsbeschränkung und des Switching-Zugs verwandelt ein Spiel mit trivialer Dominanz (Spieler 2) in ein komplexes, strategisch reichhaltiges Spiel, das für kleine $n$ von Spieler 1 dominiert wird.
Theoretische Grenzen: Die Arbeit liefert präzise asymptotische Schranken für die Komplexität des Spiels (quadratisches Wachstum der maximalen Länge) und verbindet dies mit der Struktur der Fibonacci-Zahlen.
Neue Forschungsrichtungen: Das Paper öffnet Türen für weitere Untersuchungen in Richtung:
- Beweise für optimale Strategien (Minimax-Ansätze).
- Verallgemeinerungen auf andere Rekurrenzen (z. B. $k$ -bonacci).
- Tiefergehende probabilistische Analysen der Log-Normal-Verteilung.
- Erweiterungen auf Mehrspieler- oder Koalitions-Szenarien.

Zusammenfassend stellt das „Ordered Zeckendorf Game" ein fruchtbares Testfeld dar, um die Wechselwirkung zwischen kombinatorischer Struktur, algorithmischer Komplexität und spieltheoretischer Strategie bei ganzzahligen Zerlegungen zu verstehen.