🔢 mathematics

The Ordered Zeckendorf Game

Dit paper introduceert en analyseert het geordende Zeckendorf-spel, een nieuwe tweespelercombinatorische variant die door het opleggen van volgordebeperkingen en een wisselzet een evenwichtiger strategisch landschap creëert dan de klassieke versie, waarbij wordt bewezen dat het spel altijd eindigt in de Zeckendorf-decompositie en dat de spelcomplexiteit kwadratisch groeit.

Oorspronkelijke auteurs: Ivan Bortnovskyi, Michael Lucas, Steven J. Miller, Iana Vranesko, Ren Watson, Cameron White

Gepubliceerd 2026-03-31

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Ivan Bortnovskyi, Michael Lucas, Steven J. Miller, Iana Vranesko, Ren Watson, Cameron White

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De "Zeckendorf Spel": Een Wiskundig Puzzelstukje

Stel je voor dat je een grote berg kleine stenen hebt. In dit spel zijn die stenen allemaal 1. Je doel is om deze stenen om te vormen tot een specifieke, unieke vorm die wiskundigen de "Zeckendorf-decompositie" noemen.

In de gewone wiskunde (het "klassieke spel") mag je stenen in willekeurige volgorde samenvoegen of splitsen. Maar de auteurs van dit paper hebben een nieuw, spannender versie bedacht: het geordende Zeckendorf-spel.

Hier zijn de belangrijkste regels en ontdekkingen, vertaald naar alledaagse taal:

1. De Regels: Een Kettingreactie

In het nieuwe spel staan je stenen niet in een losse hoop, maar in een rij (een rijtje). Je mag alleen met stenen spelen die direct naast elkaar staan.

Je hebt vijf manieren om te spelen:

Samenvoegen (Merging): Als je twee aangrenzende stenen hebt die samen een grotere steen vormen (bijvoorbeeld twee '1'tjes worden een '2'), mag je ze samenvoegen.
Splitsen (Splitting): Je mag een grote steen ook weer opbreken in twee kleinere, aangrenzende stukken.
Wisselen (Switching): Dit is de nieuwe, spannende regel! Als je twee stenen hebt die in de verkeerde volgorde staan (bijvoorbeeld een grote steen links van een kleine), mag je ze van plek verwisselen. Dit zorgt voor veel meer strategie, want je kunt de rij "op de kop zetten" om nieuwe combinaties te maken.

Het spel stopt pas als de rij in perfecte, oplopende volgorde staat en niemand meer iets kan veranderen.

2. Wie wint er? (De verrassing!)

In het oude, ongeordende spel was het vrij saai: als je meer dan 2 stenen had, won Speler 2 altijd. Het was als een spelletje waarbij de tweede speler altijd een valstrik had die de eerste speler niet kon ontsnappen.

In dit nieuwe, geordende spel is het echter veel spannender en eerlijker:

Voor bijna alle aantallen stenen (van 1 tot 25) wint Speler 1 (degene die begint).
Er is slechts één uitzondering: bij precies 18 stenen wint Speler 2.
De les: Door de volgorde en de mogelijkheid om te wisselen, is het spel veel onvoorspelbaarder geworden. Het is alsof je van een rechte weg naar een doolhof bent gegaan waar de eerste speler vaak de weg vindt, maar niet altijd.

3. Hoe lang duurt het spel? (De snelheidslimiet)

De onderzoekers hebben uitgerekend hoe snel of hoe langzaam het spel kan duren.

De snelste route: Als je slim speelt en direct alles samenvoegt wat kan, duurt het spel kort. De lengte is precies het aantal stenen minus het aantal stukken in de eindvorm.
De langste route: Als je probeert het spel zo lang mogelijk uit te rekken (door te wisselen en te splitsen), wordt het veel langer. De onderzoekers hebben bewezen dat de langste mogelijke game kwadratisch groeit.
- Vergelijking: Als je 10 stenen hebt, duurt het misschien 50 zetten. Heb je 100 stenen, dan kan het al snel 5.000 zetten duren. Het wordt exponentieel zwaarder naarmate je meer stenen hebt.

4. Het "Monovariant": De onzichtbare teller

Hoe weten ze zeker dat het spel ooit stopt en niet in een eeuwig rondje blijft draaien?
Ze hebben een slimme "teller" bedacht (een monovariant). Stel je voor dat elke steen in de rij een gewicht heeft, maar dat gewicht afneemt naarmate de steen verder naar rechts staat.

Elke keer dat je een zet doet (samenvoegen, splitsen of wisselen), daalt de totale som van deze gewichten.
Omdat de som nooit kan stijgen en nooit negatief kan worden, moet het spel uiteindelijk stoppen. Het is alsof je een bak met water hebt die bij elke zet een beetje leegloopt; op een gegeven moment is hij leeg en is het spel voorbij.

5. Het Geluk van het Willekeurige

Wat gebeurt er als spelers willekeurige zetten doen (zonder strategie)?
De onderzoekers hebben duizenden simulations gedaan. Ze ontdekten iets fascinerends: de lengte van deze willekeurige spellen volgt een heel specifiek patroon, genaamd een log-normale verdeling.

Vergelijking: Denk aan de grootte van zeeën of de inkomens in een land. De meeste spellen duren een gemiddelde tijd, maar er zijn een paar spellen die extreem lang duren (de "staart" van de grafiek). Het spel gedraagt zich dus als een natuurlijke, organische groei in plaats van een strakke machine.

Samenvatting

Dit paper introduceert een nieuw wiskundig spel waarbij je stenen in een rij moet ordenen. Door de regels strakker te maken (alleen aangrenzende stenen) en een nieuwe "wissel"-regel toe te voegen, is het spel van een saai, voorspelbaar spel (waar Speler 2 altijd won) veranderd in een strategisch gevecht waar Speler 1 vaak wint.

Het onderzoek laat zien dat:

Het spel altijd stopt in de juiste vorm.
De langste spellen heel lang kunnen duren (kwadratisch groeien).
Willekeurig spelen een interessant, natuurlijk patroon volgt.

Het is een mooi voorbeeld van hoe een kleine verandering in de regels (van "losse hoop" naar "geordende rij") de hele dynamiek van een spel volledig kan veranderen.

Titel: The Ordered Zeckendorf Game (Het Geordende Zeckendorf-spel)

Auteurs: Ivan Bortnovskyi, Michael Lucas, Steven J. Miller, Iana Vranesko, Ren Watson, en Cameron White.

1. Probleemstelling en Motivatie

Het artikel introduceert en analyseert een nieuwe variant van het bestaande Zeckendorf-spel, een combinatorisch tweespelersspel gebaseerd op Zeckendorf's Stelling. Deze stelling stelt dat elk positief gehele getal $n$ uniek kan worden geschreven als een som van niet-opeenvolgende Fibonacci-getallen ( $F_i$ ), waarbij $F_1=1, F_2=2, F_{i+1}=F_i+F_{i-1}$ .

In het klassieke (ongeordende) Zeckendorf-spel opereren spelers op een ongeordende multiset van Fibonacci-getallen. Het is bekend dat in deze versie Speler 2 een dominante strategie heeft voor alle $n > 2$ , wat de strategische complexiteit beperkt.

Het nieuwe probleem: De auteurs introduceren het Geordende Zeckendorf-spel. Hierbij zijn de somtermen een geordende lijst (een $n$ -tupel) en moeten alle zetten respecteren voor de volgorde van de elementen. Dit introduceert nieuwe beperkingen en dynamieken:

Alleen aangrenzende elementen kunnen worden gemerged (samengevoegd) of gesplitst.
Een nieuwe zet wordt geïntroduceerd: Switchen (het verwisselen van twee aangrenzende elementen als ze niet in oplopende volgorde staan).

Het doel is om te analyseren hoe deze ordening en de switch-mogelijkheid de speltheoretische structuur, de winnende strategieën en de lengte van het spel beïnvloeden.

2. Methodologie

De auteurs combineren theoretische bewijzen met uitgebreide computationele simulaties.

Spelregels: Het spel begint met een lijst van $n$ kopieën van $F_1$ . Spelers maken om de beurt een van de volgende zetten:
1. Mergen: $(F_i, F_{i+1}) \to F_{i+2}$ .
2. Mergen enen: $(F_1, F_1) \to F_2$ .
3. Splitsen: $(F_i, F_i) \to (F_{i-2}, F_{i+1})$ voor $i > 2$ .
4. Splitsen tweeën: $(F_2, F_2) \to (F_1, F_3)$ .
5. Switchen: $(F_i, F_j) \to (F_j, F_i)$ als $i > j$ (om de lijst weer in oplopende volgorde te brengen).
  Het spel eindigt wanneer de lijst strikt stijgend is en geen verdere merges of splits mogelijk zijn (de Zeckendorf-decompositie).
Monovarianten: Om het einde van het spel en de eindtoestand te bewijzen, construeren de auteurs een strikt afnemende monovariant (een functie die bij elke zet kleiner wordt). Deze functie combineert de "ongewenheid" (inversies) en het totale gewicht (som van de indices van de Fibonacci-getallen).
Computationele Analyse: Uitgebreide simulaties (in Python en C++) worden gebruikt om winnende strategieën te testen voor $n \le 25$ en om de verdeling van spel-lengtes bij willekeurig spelen te analyseren.

3. Belangrijkste Bijdragen en Resultaten

A. Terminatie en Eindtoestand

Stelling 1.3: Het spel terminateert altijd in een eindig aantal zetten.
Eindtoestand: De eindtoestand is uniek en komt overeen met de Zeckendorf-decompositie van $n$ , uitgedrukt als een strikt stijgende rij Fibonacci-getallen.
Bewijs: Dit wordt bewezen door de monovariant $f(S) = \sum (k+1-j)F_{i_j}$ te definiëren, die bij elke legale zet strikt afneemt.

B. Spel Lengte (Bounds)

De auteurs onderzoeken de minimale en maximale lengte van het spel.

Minimale Lengte (Kortste Spel):
- Stelling 1.4: De kortste mogelijke spel heeft lengte $n - Z(n)$ , waarbij $Z(n)$ het aantal termen in de Zeckendorf-decompositie van $n$ is.
- Dit wordt bereikt door een "gierige" strategie waarbij spelers zo snel mogelijk merges uitvoeren zonder onnodige splitsen of switches.
Maximale Lengte (Langste Spel):
- Bovenste Bound (Stelling 1.5): $M(n) \le \frac{n(n-1)}{2}$ .
- Strategie voor Lange Spelen (Definitie 1.6): De auteurs stellen een prioriteitsstrategie voor (LGS: Long Game Strategy) die switches, splitsen en merges in een specifieke volgorde uitvoert om het spel te verlengen.
- Onderste Bound (Stelling 1.10): Onder de LGS-strategie is de lengte asymptotisch:
  $M(n) \ge \frac{n^2}{2} - n \log_\phi(n) + o(n \log_\phi(n))$
- Verfijnde Bovenste Bound (Stelling 1.11):
  $M(n) \le \frac{n^2}{2} - \frac{1}{32}n \log_\phi(n) + o(n \log_\phi(n))$
- Conclusie 1.12: De asymptotische groei van de maximale spel-lengte is kwadratisch: $M(n) = \frac{n^2}{2} - \Theta(n \log_\phi(n))$ .

C. Winststrategieën en Speluitkomsten

Contrast met het klassieke spel: In tegenstelling tot het ongeordende spel (waar Speler 2 altijd wint voor $n>2$ ), is het geordende spel veel evenwichtiger.
Empirisch Resultaat: Voor alle $n \le 25$ wint Speler 1, met als enige uitzondering $n=18$ (waar Speler 2 wint).
Complexiteit: De spelboom groeit exponentieel, waardoor het vinden van een algemene winnende strategie voor grote $n$ computationeel zeer uitdagend is. De auteurs vermoeden dat Speler 1 een significant voordeel heeft, maar een formele bewering voor alle $n$ blijft een open probleem.

D. Probabilistisch Gedrag

Conjecture 3.2: Bij willekeurig spelen (waar elke legale zet even waarschijnlijk is), convergeert de verdeling van het aantal zetten naar een log-normale verdeling.
Simulaties voor $n=150$ tonen zware staarten en rechts-scheef gedrag, consistent met een log-normale verdeling. Ook wijzen de uitkomsten erop dat bij willekeurig spelen beide spelers even vaak winnen.

4. Significantie en Toekomstige Richtingen

Dit werk verrijkt het landschap van getaltheoretische spellen door de introductie van orde en switch-moves. De belangrijkste implicaties zijn:

Strategische Diepgang: De invoering van orde en de switch-mogelijkheid herstelt het evenwicht tussen de spelers en creëert een veel complexer strategisch landschap dan het klassieke spel.
Combinatorische Structuur: De analyse van de maximale spel-lengte onthult subtiele structuren in de herhaling van Fibonacci-termen tijdens het spel (Lemma 1.9).
Open Vragen:
- Kan de optimaliteit van de "Long Game Strategy" formeel worden bewezen?
- Bestaat er een algemene winnende strategie voor Speler 1 of Speler 2 voor alle $n$ ?
- Hoe gedragen deze spellen zich bij generalisaties (bijv. $k$ -bonacci getallen of niet-constante recurrenties)?
- Kan de log-normale verdeling van willekeurige spel-lengtes wiskundig worden afgeleid?

Het artikel biedt een rijk fundament voor verdere exploratie in combinatorische speltheorie, algoritmen en dynamische systemen, met open source code beschikbaar voor replicatie en uitbreiding.