论文标题
确定性的Zeckendorf游戏
Deterministic Zeckendorf Games
论文作者
论文摘要
Zeckendorf证明，每个积极整数都可以独特地写入非阳性斐波那契数的总和。我们进一步探索了在Baird-Smith，Epstein，Flint和Miller中引入的两个玩家Zeckendorf游戏：给定固定整数$ n $，并且初始分解为$ n = nf_1 $，玩家使用与重新配置$ f_ {n + 1} = f_n + 1} = f_n + f_n + f_ + f_ + f _ n _ n _ n _ n_1}的动作进行交替。我们改善了可能的移动次数的上限，并表明它的顺序与下限$ n $相同；这是对数比以前的工作的改进。新的上限为$ 3n -3z（n）-iz（n） + 1 $，并且现有下限在$ n -z（n）$移动时呈锋利，其中$ z（n）$是zeckendorf分解$ n $ and $ iz（n）$中的术语数量，是$ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $ n $。我们还研究了游戏的四个确定性变体，其中有一个固定的订单，其中可用的移动采取了：结合最大，最大的，最小和最小的组合。我们证明，最大和最大的结合了下限。拆分最小的是所有可能的游戏中最多的动作，并且接近新的上限。对于组合分式游戏，动作数量与$ n $线性增长。
Zeckendorf proved that every positive integer can be written uniquely as the sum of non-adjacent Fibonacci numbers. We further explore a two-player Zeckendorf game introduced in Baird-Smith, Epstein, Flint, and Miller: Given a fixed integer $n$ and an initial decomposition of $n = nF_1$, players alternate using moves related to the recurrence relation $F_{n+1} = F_n + F_{n_1}$, and the last player to move wins. We improve the upper bound on the number of moves possible and show that it is of the same order in $n$ as the lower bound; this is an improvement by a logarithm over previous work. The new upper bound is $3n - 3Z(n) - IZ(n) + 1$, and the existing lower bound is sharp at $n - Z(n)$ moves, where $Z(n)$ is the number of terms in the Zeckendorf decomposition of $n$ and $IZ(n)$ is the sum of indices in the same Zeckendorf decomposition of $n$. We also studied four deterministic variants of the game, where there was a fixed order on which available move one takes: Combine Largest, Split Largest, Combine Smallest and Split Smallest. We prove that Combine Largest and Split Largest realize the lower bound. Split Smallest has the largest number of moves over all possible games, and is close to the new upper bound. For Combine Split games, the number of moves grows linearly with $n$.
