🔢 mathematics

The Ordered Zeckendorf Game

This paper introduces and analyzes the ordered Zeckendorf game, a two-player combinatorial variant that enforces summand ordering and adjacency constraints, resulting in a more balanced strategic landscape where Player 1 wins for most small values, while establishing that the game always terminates in the ascending Zeckendorf decomposition with move counts ranging linearly to quadratically.

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

Published 2026-03-31

📖 5 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a giant pile of identical building blocks. In the world of math, these blocks are called Fibonacci numbers (1, 2, 3, 5, 8, 13...). There's a famous rule in math called Zeckendorf's Theorem, which says that no matter how many blocks you have, you can always rearrange them into a unique "perfect tower" where no two blocks are the same size and no two blocks are next to each other in size (like you can't have a 5 and an 8 right next to each other; you'd have to combine them into a 13).

For a long time, mathematicians studied a game based on this rule. In the old version of the game, players could grab any two blocks from the pile, smash them together, or split them apart, regardless of where they were sitting. It turned out that in this chaotic, "grab anything" game, the second player could almost always win. It was like playing checkers where the second player knew a secret trick to win every single time.

The authors of this paper decided to spice things up. They created the Ordered Zeckendorf Game.

The New Rules: A Line of People

Instead of a messy pile of blocks, imagine the blocks are people standing in a single-file line.

The Goal: The game starts with a line of $n$ people, all holding a tiny "1" block. The goal is to reach the "Perfect Tower" state, but the people must stay in a line.
The Moves: You can only interact with neighbors.
1. Merge: If two neighbors have compatible blocks (like a 3 and a 5), they can combine into a bigger block (an 8).
2. Split: If a neighbor has a big block, they can break it into two smaller ones, but they have to fit into the line.
3. The New Twist (Switching): This is the game-changer. If two neighbors are out of order (like a big block standing in front of a small one), you can swap them. This allows players to rearrange the line to set up future moves.

Why This Changes Everything

In the old game, the second player had a "dominant strategy" (a cheat code to win). But in this new Ordered Game, the rules are much stricter because you can only touch your neighbors.

The authors found something surprising: The first player is now the favorite!

For almost every starting number of blocks (up to 25), the first player can force a win.
There is only one weird exception (when you start with 18 blocks), where the second player can still win.
The Metaphor: Think of the old game as a free-for-all dance where the second dancer always knew the steps. The new game is like a conga line where you can only hold the hands of the people next to you. Suddenly, the person leading the line (Player 1) has the advantage because they can set up the moves before the second player can react.

How Long Does the Game Last?

The paper also asks: What is the shortest and longest this game can possibly take?

The Shortest Game: If players are super efficient and just smash blocks together as fast as possible, the game ends quickly. The length is simply the starting number minus the number of blocks in the final "Perfect Tower."
The Longest Game: If players are trying to drag the game out (maybe to annoy their opponent), they can make the game last a very long time. The authors proved that the game length grows like a square of the starting number.
- Analogy: If you start with 10 blocks, the game might last 100 moves. If you start with 100 blocks, it could last 10,000 moves. It gets huge very fast.

The "Magic" of the Game

The authors proved two main things:

It Always Ends: No matter how crazy the players get, swapping and splitting, the game must eventually stop. It can't go on forever. It always ends in that unique "Perfect Tower" arrangement. They proved this using a "magic counter" (called a monovariant) that goes down every time a move is made, ensuring the game runs out of moves eventually.
Random Play is Weird: If two players just pick random legal moves without thinking, the number of turns it takes to finish the game follows a specific pattern called a log-normal distribution.
- Analogy: Imagine dropping a ball down a bumpy hill. Sometimes it rolls straight down fast. Sometimes it gets stuck in a groove and bounces around for a long time. Most games will be somewhere in the middle, but there's a "long tail" of games that take a very long time to finish.

The Big Picture

This paper is like discovering a new board game that looks simple but has deep, hidden strategies.

Old Game: Predictable, second-player wins.
New Game: Unpredictable, first-player wins, and the strategy depends heavily on the order of the pieces.

The authors didn't just play the game; they mapped out the entire landscape. They showed how long games can get, proved the game always finishes, and even guessed that if you play randomly, the results look like a specific mathematical curve.

In short: By adding a simple rule about "order" and "neighbors" to a classic math game, the authors turned a boring, predictable contest into a complex, strategic battle where the first player usually has the upper hand, and the game can stretch out into a massive, quadratic marathon.

1. Problem Definition and Motivation

Context:
The paper investigates a combinatorial two-player game based on Zeckendorf's Theorem, which states that every positive integer $n$ has a unique representation as a sum of non-consecutive Fibonacci numbers ( $F_1=1, F_2=2, F_{i+1}=F_i+F_{i-1}$ ).

The Classical Game:
In the previously studied "Zeckendorf Game," players start with an unordered multiset of $n$ ones ( $F_1$ ). They perform merge and split operations (e.g., $F_i + F_{i+1} \to F_{i+2}$ or $F_i + F_i \to F_{i+1} + F_{i-2}$ ) until the unique Zeckendorf decomposition is reached.

Limitation: In the classical unordered version, Player 2 has a dominant winning strategy for all $n > 2$ , rendering the game strategically shallow.

The Ordered Variant:
The authors introduce the Ordered Zeckendorf Game, where the state is an ordered tuple of Fibonacci numbers.

Constraints: Moves are restricted to adjacent elements only.
New Move: A Switching move is introduced, allowing players to swap adjacent elements $(F_i, F_j) \to (F_j, F_i)$ if $i > j$ (i.e., to restore ascending order).
Goal: The game ends when the tuple is strictly increasing and no further merges or splits are possible (the Zeckendorf decomposition in ascending order).

Research Question: How does imposing order and adjacency constraints alter the game's termination, length, and strategic balance compared to the classical version?

2. Methodology

The authors employ a hybrid approach combining theoretical proofs (using monovariants and induction) and computational simulations (exhaustive search for small $n$ and Monte Carlo simulations for probabilistic analysis).

A. Theoretical Framework

Monovariants: To prove termination and bound game length, the authors define a strictly decreasing function $f(S)$ for a state $S = (F_{i_1}, \dots, F_{i_k})$ :
$f(S) = \sum_{j=1}^k (k + 1 - j)F_{i_j}$
This function weights terms by their position and value, ensuring that every legal move (merge, split, or switch) strictly decreases the total value.
State-Transition Graphs: For analyzing maximal game length, the authors define "Pivot States" based on the repetition of higher-index terms ( $F_i$ for $i \ge 3$ ). They construct a directed graph to track transitions between states with "No Repetitions" and states with specific repetitions (e.g., $F_3, F_3$ ).
Strategy Analysis: They propose a specific "Long Game Strategy" (LGS) prioritizing switches, then combining ones, then splitting from the right, and merging from the left.

B. Computational Analysis

Exhaustive Search: Used to determine winning strategies for $n \le 25$ .
Random Simulations: 10,000+ random games were simulated for large $n$ (e.g., $n=150$ ) to analyze move distribution and win probabilities.
Codebase: Implemented in Python and C++ (publicly available).

3. Key Contributions and Results

A. Termination and Final State

Theorem 1.3: The game always terminates in a finite number of moves.
Final State: The game invariably ends in the unique Zeckendorf decomposition of $n$ , expressed as a strictly increasing sequence.
Proof: Relies on the strictly decreasing monovariant $f(S)$ , which prevents cycles and forces convergence to the unique state where no moves are possible.

B. Game Length Bounds

The paper establishes tight bounds on the number of moves $M(n)$ :

Shortest Game (Lower Bound):
- Result: The minimum length is exactly $n - Z(n)$ , where $Z(n)$ is the number of terms in the Zeckendorf decomposition of $n$ .
- Mechanism: Achieved via a greedy strategy that merges adjacent pairs immediately without unnecessary splits or switches.
Longest Game (Upper and Lower Bounds):
- Upper Bound: $M(n) \le \frac{n(n-1)}{2}$ .
- Refined Upper Bound: $M(n) \le \frac{n^2}{2} - \frac{1}{32}n \log_\phi n + o(n \log_\phi n)$ .
- Lower Bound: The authors prove that the "Long Game Strategy" (LGS) yields a length of at least $\frac{n^2}{2} - n \log_\phi n + o(n \log_\phi n)$ .
- Asymptotic Characterization: $M(n) = \frac{n^2}{2} - \Theta(n \log_\phi n)$ .
- Significance: The game length grows quadratically, but the logarithmic correction term is significant.

C. Winning Strategies and Strategic Balance

Shift in Dynamics: Unlike the classical game (where Player 2 wins for $n > 2$ ), the ordered variant is highly balanced.
Empirical Findings:
- For $n \le 25$ , Player 1 wins in all cases except $n=18$ (where Player 2 wins).
- This suggests the introduction of order and switching restores strategic depth and gives Player 1 a significant advantage for small $n$ .
Open Problem: A general winning strategy for arbitrary $n$ remains unproven due to the combinatorial explosion of the game tree.

D. Probabilistic Behavior

Conjecture 3.2: Under uniform random play, the distribution of game lengths converges to a log-normal distribution as $n \to \infty$ .
Evidence: Simulations for $n=150$ show heavy-tailed, right-skewed distributions consistent with log-normal behavior.
Win Probability: Under random play, the win probability for both players appears to approach 0.5, indicating symmetry in the random dynamics.

4. Significance and Future Directions

Significance:

Theoretical Depth: The paper demonstrates that adding simple constraints (order and adjacency) to a known number-theoretic game fundamentally changes its complexity, moving it from a solved, trivial game to one with rich strategic and probabilistic properties.
Algorithmic Challenge: The game serves as a testbed for algorithmic game theory, requiring deep lookahead and heuristic pruning (e.g., Alpha-Beta) to solve for larger $n$ .
New Invariants: The construction of the specific monovariant $f(S)$ provides a novel tool for analyzing games involving Fibonacci recurrences.

Open Questions & Future Work:

Optimal Strategy Proof: Rigorously proving the existence of a winning strategy for Player 1 (or identifying the pattern of exceptions like $n=18$ ) for all $n$ .
LGS Optimality: Proving that the proposed "Long Game Strategy" is indeed optimal for maximizing game length.
Generalizations: Extending the ordered game to $k$ -bonacci sequences or non-constant recurrence relations.
Probabilistic Rigor: Deriving the log-normal distribution of move counts mathematically rather than empirically.
Multiplayer Variants: Exploring how order constraints affect games with more than two players or cooperative alliances.

In summary, the Ordered Zeckendorf Game transforms a static number-theoretic decomposition into a dynamic, strategic, and probabilistically rich combinatorial game, offering new avenues for research in additive number theory and algorithmic game theory.