Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2508.20222 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911549312991232 |
|---|---|
| author | Bortnovskyi, Ivan Lucas, Michael Miller, Steven J. Vranesko, Iana Watson, Ren White, Cameron |
| author_facet | Bortnovskyi, Ivan Lucas, Michael Miller, Steven J. Vranesko, Iana Watson, Ren White, Cameron |
| contents | We introduce and analyze the ordered Zeckendorf game, a novel combinatorial two-player game inspired by Zeckendorf's Theorem, which guarantees a unique decomposition of every positive integer as a sum of non-consecutive Fibonacci numbers. Building on the original Zeckendorf game\ -- previously studied in the context of unordered multisets\ -- we impose a new constraint: all moves must respect the order of summands. The result is a richer and more nuanced strategic landscape that significantly alters game dynamics.
Unlike the classical version, where Player 2 has a dominant strategy for all $n > 2$, our ordered variant reveals a more balanced and unpredictable structure. In particular, we find that Player 1 wins for nearly all values $n \leq 25$, with a single exception at $n = 18$. This shift in strategic outcomes is driven by our game's key features: adjacency constraints that limit allowable merges and splits to neighboring terms, and the introduction of a switching move that reorders pairs.
We prove that the game always terminates in the Zeckendorf decomposition\ -- now in ascending order\ -- by constructing a strictly decreasing monovariant. We further establish bounds on game complexity: the shortest possible game has length exactly $n - Z(n)$, where $Z(n)$ is the number of summands in the Zeckendorf decomposition of $n$, while the longest game exhibits quadratic growth, with $M(n) \sim \frac{n^2}{2}$ as $n \to \infty$.
Empirical simulations suggest that random game trajectories exhibit log-normal convergence in their move distributions. Overall, the ordered Zeckendorf game enriches the landscape of number-theoretic games, posing new algorithmic challenges and offering fertile ground for future exploration into strategic complexity, probabilistic behavior, and generalizations to other recurrence relations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20222 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Ordered Zeckendorf Game Bortnovskyi, Ivan Lucas, Michael Miller, Steven J. Vranesko, Iana Watson, Ren White, Cameron Number Theory Combinatorics We introduce and analyze the ordered Zeckendorf game, a novel combinatorial two-player game inspired by Zeckendorf's Theorem, which guarantees a unique decomposition of every positive integer as a sum of non-consecutive Fibonacci numbers. Building on the original Zeckendorf game\ -- previously studied in the context of unordered multisets\ -- we impose a new constraint: all moves must respect the order of summands. The result is a richer and more nuanced strategic landscape that significantly alters game dynamics. Unlike the classical version, where Player 2 has a dominant strategy for all $n > 2$, our ordered variant reveals a more balanced and unpredictable structure. In particular, we find that Player 1 wins for nearly all values $n \leq 25$, with a single exception at $n = 18$. This shift in strategic outcomes is driven by our game's key features: adjacency constraints that limit allowable merges and splits to neighboring terms, and the introduction of a switching move that reorders pairs. We prove that the game always terminates in the Zeckendorf decomposition\ -- now in ascending order\ -- by constructing a strictly decreasing monovariant. We further establish bounds on game complexity: the shortest possible game has length exactly $n - Z(n)$, where $Z(n)$ is the number of summands in the Zeckendorf decomposition of $n$, while the longest game exhibits quadratic growth, with $M(n) \sim \frac{n^2}{2}$ as $n \to \infty$. Empirical simulations suggest that random game trajectories exhibit log-normal convergence in their move distributions. Overall, the ordered Zeckendorf game enriches the landscape of number-theoretic games, posing new algorithmic challenges and offering fertile ground for future exploration into strategic complexity, probabilistic behavior, and generalizations to other recurrence relations. |
| title | The Ordered Zeckendorf Game |
| topic | Number Theory Combinatorics |
| url | https://arxiv.org/abs/2508.20222 |