2020/09/20 by Anna Cusenza, Cusenza, Anna, Aiden Dunkelberg +17
Computer Science · Mathematics · Physics and Astronomy · #Advanced Combinatorial Mathematics #Advanced Mathematical Theories and Applications #FOS: Mathematics #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2009.09510
openalex publication_date 2020/09/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Zeckendorf proved that every positive integer n can be written uniquely as the sum of non-adjacent Fibonacci numbers. We use this decomposition to construct a two-player game. Given a fixed integer n and an initial decomposition of n=n F1, the two players alternate by using moves related to the recurrence relation Fn+1=Fn+Fn-1, and whoever moves last wins. The game always terminates in the Zeckendorf decomposition; depending on the choice of moves the length of the game and the winner can vary, though for n≥ 2 there is a non-constructive proof that Player 2 has a winning strategy. Initially the lower bound of the length of a game was order n (and known to be sharp) while the upper bound was of size n log n. Recent work decreased the upper bound to of size n, but with a larger constant than was conjectured. We improve the upper bound and obtain the sharp bound of (√(5)+3)/(2) n - IZ(n) - (1+√(5))/(2)Z(n), which is of order n as Z(n) is the number of terms in the Zeckendorf decomposition of n and IZ(n) is the sum of indices in the Zeckendorf decomposition of n (which are at most of sizes log n and log2 n respectively). We also introduce a greedy algorithm that realizes the upper bound, and show that the longest game on any n is achieved by applying splitting moves whenever possible.