The Zeckendorf Game

DOI10.1007/978-3-030-31106-3_3MaRDI QIDQ3296085zbMATH OpenOpenAlexFDO

Authors Paul Baird-Smith, Alyssa Epstein, Kristen Flint, Steven J. Miller

Publication date 3 July 2020

Published in Combinatorial and Additive Number Theory III (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.04881

zbMATH Keywords

Fibonacci numbersgame theoryZeckendorf decomposition

Mathematics Subject Classification ID

Fibonacci and Lucas numbers and polynomials and generalizations (11B39) 2-person games (91A05) Combinatorial games (91A46)

Abstract: Zeckendorf proved that every positive integer $n$ can be written uniquely as the sum of non-adjacent Fibonacci numbers. We use this to create a two-player game. Given a fixed integer $n$ and an initial decomposition of $n=n{F}_1$, the two players alternate by using moves related to the recurrence relation $F_{n+1}=F_n+F_{n-1}$, and whoever moves last wins. The game always terminates in the Zeckendorf decomposition, though depending on the choice of moves the length of the game and the winner can vary. We find upper and lower bounds on the number of moves possible. The upper bound is on the order of $nlogn$, and the lower bound is sharp at $n-Z(n)$ moves, where $Z(n)$ is the number of terms in the Zeckendorf decomposition of $n$. Notably, Player 2 has the winning strategy for all $n>2$; interestingly, however, the proof is non-constructive.

Recommendations

• The generalized Zeckendorf game
• scientific article; zbMATH DE number 7676353
• Z-domination game
• The Borell-Ehrhard game
• The Magnus-Derek game
• Schützenberger's jeu de taquin
• The game of End-Wythoff
• Bounds on Zeckendorf games
• The game of End-Nim
• scientific article; zbMATH DE number 2162206

Cites work

• From Fibonacci numbers to central limit type theorems
• Gaussian behavior in generalized Zeckendorf decompositions
• scientific article; zbMATH DE number 3373770 (Why is no real title available?)
• scientific article; zbMATH DE number 3378996 (Why is no real title available?)
• The generalized Zeckendorf game

Cited in

(19)

• Global Fibonacci nim
• The Borell-Ehrhard game
• Completeness of positive linear recurrence sequences
• An Ehrenfeucht-Fraïssé class game
• scientific article; zbMATH DE number 2162206 (Why is no real title available?)
• Extending Zeckendorf's theorem to a non-constant recurrence and the Zeckendorf game on this non-constant recurrence relation
• Deterministic Zeckendorf games
• The generalized Zeckendorf game
• Bounds on Zeckendorf games
• The Fibonacci quilt game
• The Lion and the Christian, and Other Pursuit and Evasion Games
• scientific article; zbMATH DE number 7676353 (Why is no real title available?)
• The game of End-Nim
• More on the Magnus-Derek game
• The accelerated Zeckendorf game
• Fixed-term decompositions using even-indexed Fibonacci numbers
• The Reversed Zeckendorf Game
• Towards the Gaussianity of random Zeckendorf games
• Black hole Zeckendorf games

This page was built for publication: The Zeckendorf Game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3296085)