论文标题
迈向随机Zeckendorf游戏的高斯性
Towards the Gaussianity of Random Zeckendorf Games
论文作者
论文摘要
Zeckendorf证明，任何正整数都具有唯一的分解，作为非连续斐波那契数的总和，由$ f_1 = 1，f_2 = 2，f_2 = 2，f_ {n + 1} = f_n + f_n + f_ {n-1} $索引。在这个结果的激励下，Baird，Epstein，Flint和Miller定义了两个玩家Zeckendorf游戏，在那里，两名玩家轮流在斐波那契数字上行动，这些数字总是总计为$ n $。游戏在没有可能的动作时终止，而最终的球员将赢得胜利。值得注意的是，研究了随机游戏的设置：该游戏是通过随机选择可用的动作来进行的，他们猜想是输入$ n \ to \ infty $，随机游戏长度的分布会收敛到高斯。 我们证明，某些移动计数总和是恒定的，并且在涉及加泰罗尼亚人数的输入$ n $上找到了最短游戏数量的下限。 Baird等人的作品。和Cuzensa等。确定如何在给定的输入$ n $上分别实现最短，最长的Zeckendorf游戏：我们确定，对于任何输入$ n $，可能的游戏长度范围构成了自然数的间隔：可以实现最短和最长的游戏长度之间的每个游戏长度。 我们进一步研究了随机Zeckendorf游戏的概率方面。我们研究了所有Zeckendorf游戏在输入$ n $：统一度量的空间上的概率措施，以及通过在任何给定位置随机选择移动而引起的措施。根据这两种措施，在限制$ n \ to \ infty $中，两个玩家都以$ 1/2 $的概率获胜。我们还发现了固定输入$ n $的所有Zeckendorf游戏集合的自然分区，我们在其上观察到较弱的融合到限制$ n \ to \ infty $中的高斯。我们以许多开放的问题结束了工作。
Zeckendorf proved that any positive integer has a unique decomposition as a sum of non-consecutive Fibonacci numbers, indexed by $F_1 = 1, F_2 = 2, F_{n+1} = F_n + F_{n-1}$. Motivated by this result, Baird, Epstein, Flint, and Miller defined the two-player Zeckendorf game, where two players take turns acting on a multiset of Fibonacci numbers that always sums to $N$. The game terminates when no possible moves remain, and the final player to perform a move wins. Notably, studied the setting of random games: the game proceeds by choosing an available move uniformly at random, and they conjecture that as the input $N \to \infty$, the distribution of random game lengths converges to a Gaussian. We prove that certain sums of move counts is constant, and find a lower bound on the number of shortest games on input $N$ involving the Catalan numbers. The works Baird et al. and Cuzensa et al. determined how to achieve a shortest and longest possible Zeckendorf game on a given input $N$, respectively: we establish that for any input $N$, the range of possible game lengths constitutes an interval of natural numbers: every game length between the shortest and longest game lengths can be achieved. We further the study of probabilistic aspects of random Zeckendorf games. We study two probability measures on the space of all Zeckendorf games on input $N$: the uniform measure, and the measure induced by choosing moves uniformly at random at any given position. Under both measures that in the limit $N \to \infty$, both players win with probability $1/2$. We also find natural partitions of the collection of all Zeckendorf games of a fixed input $N$, on which we observe weak convergence to a Gaussian in the limit $N \to \infty$. We conclude the work with many open problems.
