TOWARDS THE GAUSSIANITY OF RANDOM ZECKENDORF GAMES JUSTIN CHEIGH GUILHERME ZEUS DANTAS E MOURA RYAN JEONG JACOB LEHMANN DUKE WYATT MILGRIM STEVEN J. MILLER PRAKOD NGAMLAMAI

2025-05-06 0 0 523.21KB 29 页 10玖币

侵权投诉

TOWARDS THE GAUSSIANITY OF RANDOM ZECKENDORF GAMES

JUSTIN CHEIGH, GUILHERME ZEUS DANTAS E MOURA, RYAN JEONG, JACOB LEHMANN

DUKE, WYATT MILGRIM, STEVEN J. MILLER, PRAKOD NGAMLAMAI

Abstract. Zeckendorf proved that any positive integer has a unique decomposition as

a sum of non-consecutive Fibonacci numbers, indexed by F1= 1, F2= 2, Fn+1 =Fn+

Fn−1. Motivated by this result, Baird, Epstein, Flint, and Miller [3] deﬁned 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 ﬁnal

player to perform a move wins. Notably, [3] 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→ ∞, the distribution of random game lengths converges to a Gaussian.

We prove that certain sums of move counts is constant, and ﬁnd a lower bound on the

number of shortest games on input Ninvolving the Catalan numbers. The works [3] and

Cuzensa et al. [5] 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→ ∞, both players win with probability

1/2. We also ﬁnd natural partitions of the collection of all Zeckendorf games of a ﬁxed input

N, on which we observe weak convergence to a Gaussian in the limit N→ ∞. We conclude

the work with many open problems.

Contents

1. Introduction 2

1.1. Prior Work 2

1.2. Notation and Conventions 3

1.3. Main Results 4

2. Structural Results 5

2.1. Combinatorial Observations 5

2.2. Shortest Games 8

3. The Set of Possible Game Lengths Constitute An Interval 10

4. Winning Odds in the Limit N→ ∞ 15

4.1. Overview 15

4.2. Partitioning the Collection of Possible Games 15

4.3. Analysis 17

4.4. Extending the Partition on ΩN22

5. Weak Convergence of Random Game Lengths as N→ ∞ 24

6. Open Problems 26

6.1. Other Two-Player Games Based on Recurrences 26

arXiv:2210.11038v1 [math.CO] 20 Oct 2022

2 CHEIGH, DANTAS E MOURA, JEONG, LEHMANN DUKE, MILGRIM, MILLER, NGAMLAMAI

6.2. Towards Gaussianity: Other Approaches 27

6.3. Towards Gaussianity: Mixing 27

Acknowledgements 28

References 28

1. Introduction

The Fibonacci numbers are widely considered to be the most interesting and well-known

recursive sequence in mathematics. In this article, we shall index the Fibonacci numbers by

F1= 1, F2= 2, and for general n≥3, Fn=Fn−1+Fn−2. Zeckendorf proved the following

fundamental theorem: the decomposition in the proceeding theorem is referred to as the

Zeckendorf decomposition of the positive integer N.

Theorem 1.1 ([9]).Every positive integer Ncan be decomposed uniquely into a sum of

distinct, non-consecutive Fibonacci numbers.

Inspired by this result, the authors of [3] constructed the two-player Zeckendorf game.

Deﬁnition 1.2 ([3]).Given input N∈N, the Zeckendorf game is played on a multiset of

Fibonacci numbers, initialized at S={FN

1}. On each turn, a player can act on the multiset

by performing one of the following moves if it is available.

(1) If we have two consecutive Fibonacci numbers Fk−1, Fkfor some k≥2, then we can

replace them by Fk+1, denoted Fk−1∧Fk→Fk+1.

(2) If we have two instances of the same Fibonacci number Fk, then

(a) If k= 1, we can play F1∧F1→F2.

(b) If k= 2, we can play F2∧F2→F1∧F3.

The two players alternate turns until no playable moves remain. The last player to move

wins the game.

Observe that the moves of the game are consistent with the Fibonacci recurrence: we

either combine two consecutive terms, or split terms with multiple instances. Perhaps more

intuitively, we can understand the game as acting on a row of bins, with bin kcorresponding

to the Fibonacci number Fkand its height being the multiplicity of Fkin the multiset.

1.1. Prior Work. The article [3] introduces the two-player Zeckendorf game, determine

upper and lower bounds on the length of a game on input N(showing in particular that

the game always terminates), and shows non-constructively that Player 2 has the winning

strategy for all N≥2. In particular, they provide the following explicit formula for the length

of the shortest Zeckendorf game on input N, achieved by only playing combine moves.

Theorem 1.3 ([3]).The number of combine moves in any Zeckendorf game on input Nis

is N−Z(N). Furthermore, any such shortest game terminates in N−Z(N) moves, where

Z(N) is the number of terms in the Zeckendorf decomposition of N.

The works [7] and [5] successively improved the upper bound of [3] on the length of a

Zeckendorf game on ﬁxed input N; the former article ﬁnds a deterministic game which has

longest possible length for input N, while the latter generalizes this paradigm. We frequently

TOWARDS THE GAUSSIANITY OF RANDOM ZECKENDORF GAMES 3

make use of the following two results from [5] in our arguments. We note that although the

following result provides a strategy to achieve a longest game, ﬁnding a convenient closed

form for the length of the longest game for non-Fibonacci input Nremains open (with the

case of Fibonacci input treated by [5]).

Theorem 1.4 ([5]).The longest game on any Nis achieved by applying split moves or

combine 1s (in any order) whenever possible, and, if there is no split or combine 1 move

available, combine consecutive indices from smallest to largest.

Theorem 1.5 ([5]).A Zeckendorf game on input Ncan be played with strictly splitting

and combine 1 moves if and only if N=Fk−1 for some k≥2.

Finally, we remark that analogous two-player games have been developed for other recur-

rences: the work [2] extends [3] by deﬁning and studying such games for recursive sequences

deﬁned by linear recurrence relations of form Gn=Pk

i=1 cGn−i(c=k−1 = 1 yielding

the Fibonacci numbers), again giving lower and upper bounds on game lengths (including

showing termination) and showing non-constructively that Player 2 has a winning strategy,

while [4] similarly studies recurrences of form an+1 =nan+an−1.

1.2. Notation and Conventions. We let C1denote the combine move F1∧F1→F2, and

(for k≥2) let Ckdenote the combine move Fk−1∧Fk→Fk+1. Let S2denote the splitting

move 2F2→F1∧F3, and (for k≥3) let Skdenote the splitting move 2Fk→Fk−2∧Fk+1.

We preﬁx a particular type of move with Mto denote the number of such moves (e.g. MC1

denotes the number of C1’s in a game).

We let Z(N) denote the number of terms in the Zeckendorf decomposition of N. We

loosely refer to the number of instances of Fkas the height of bin k, denoted hk; it will

usually be clear from context at which point in the game the quantity hkrefers to. When

discussing the height of bin kafter a speciﬁc number mof moves in the game, we notate

this by hk(m). For λ∈N, we shall also occasionally use the shorthand [λ] = {1,2, . . . , λ}.

In this work, we shall generally work under the assumption that Fn≤N < Fn+1 for some

n∈N(i.e., nis the index of the largest Fibonacci number that is no larger than N)1. While

proving Theorem 1.9, we occasionally refer to moves C1, S2, . . . , Sn−1as Type A moves,

and all other moves (namely, moves Ckfor k≥2) as Type B moves. The work [5] also

achieved an understanding of precisely when playing strictly Type A moves throughout the

whole game is possible.

Finally, the present article furthers the study of random Zeckendorf games. Here, we let

ΩNdenotes the (ﬁnite) collection of all Zeckendorf games on input N, with FN= 2ΩNthe

associated σ-algebra, and express a given Zeckendorf game G ∈ ΩNas a (ﬁnite) sequence of

λmoves, written as G= (M1, M2, . . . , Mλ). We study two probability measures to complete

the space (ΩN,FN): the uniform measure µN, deﬁned by

µN(G) = 1

|ΩN|for all G ∈ ΩN

and the probability measure PNinduced by choosing, at every conﬁguration along a given

game, uniformly at random among available moves, deﬁned by

PN(G) =

k=1

num. playable moves after (M1, . . . , Mk−1)for G= (M1, M2, . . . , Mλ)∈ΩN.

1This is why we have elected to deviate from notation traditionally used in papers concerning this game.

4 CHEIGH, DANTAS E MOURA, JEONG, LEHMANN DUKE, MILGRIM, MILLER, NGAMLAMAI

All of the results we derive in this context apply to both probability spaces.

1.3. Main Results. The work [5] determines an upper bound on the length of a game on

input N. We improve this upper bound using similar techniques as in the work [3].

Theorem 1.6. The length of a Zeckendorf game on input Nis upper-bounded by

ϕ2N−ZI(N)−2Z(N)+(ϕ−1)

where ZI(N) represents the index sum of the Zeckendorf decomposition of N. Furthermore,

the bound is sharp for inﬁnitely many N.

Much of our work was inspired by the following conjecture (the only one still unresolved

in the paper it was introduced in), initially posed by [3], which concerns distributional

properties of the length of random Zeckendorf games on input Nin the limit N→ ∞.

Conjecture 1.7 ([3,7]).In the limit N→ ∞, the distribution of the number of moves

in a random Zeckendorf game on input Nconverges to a Gaussian, with expectation and

variance approximately 0.215N.2

As such, many of our main results have largely arisen from attempting to understand those

aspects of Zeckendorf games which may potentially aid in resolving the aforementioned con-

jecture (and in striving to determine what such aspects are). First, we have the following

lower bound on the number of shortest Zeckendorf games of length N. Intuitively, if the

distribution of random game lengths were indeed Gaussian, this should be an extreme un-

derestimate compared to the number of ways to achieve other game lengths (shortest games

involve the fewest number of decisions, so one might naturally expect that the probability

of achieving one via a random game is larger than longer games), yet it still explodes in N.

Theorem 1.8. Let Fn≤N < Fn+1. Then the number of shortest Zeckendorf games with

input Nis at least Qn−2

k=1 Cat(Fk), where Cat(Fk) denotes the Fkth Catalan number.

The shortest game and longest game were studied in [3] and [5], respectively. It is natural

to ask whether every game length between the shortest and longest game length is achievable:

we resolve this in the aﬃrmative.

Theorem 1.9. For any input Nto the Zeckendorf game, let Mdenote the length of the

longest Zeckendorf game with input N. Then for any msatisfying N−Z(N)≤m≤M,

there exists a Zeckendorf game of length mon input N. In other words, the set of achievable

game lengths constitutes an interval in the natural numbers.

We also study the winning odds of players in the limit N→ ∞ of inﬁnite input when

studying random Zeckendorf games, for which one might expect that both players win with

probability 1/2 in the limit if if Conjecture 1.7 holds as the variance of the conjectured

Gaussian grows with N. We establish that this is indeed true by proving a much more

general result: we can understand Theorem 1.10 as saying that in the limit of inﬁnite input,

aZ-player random Zeckendorf game is fair, in the sense that all Zplayers have the same

probability of winning.

2The authors of [3] posed this conjecture based on numerical data gathered from 9,999 simulations of a

random game with n= 18. The authors of [7] gathered further numerical evidence with a sample of 1,000

games with n= 1,000,000. We ran a brute force enumeration over all possible games for n≤18 and found

the distribution of lengths appeared to be Gaussian. This is a slightly diﬀerent problem than the random

game though is closely related.

TOWARDS THE GAUSSIANITY OF RANDOM ZECKENDORF GAMES 5

Theorem 1.10. For any integer Z≥1 and z∈ {0,1, . . . , M −1}, we have that

lim

N→∞ µN(Game length equals zmod Z) = lim

N→∞

PN(Game length equals zmod Z) = 1

Taking Z= 2 in Theorem 1.10 above yields the following result for the classical two-player

Zeckendorf game.

Theorem 1.11. For the two-player Zeckendorf game, in the limit N→ ∞ under both

probability measures µNand PN, Player 1 and Player 2 are equally likely to win. Explicitly,

lim

N→∞ µN(Player 1 wins) = lim

N→∞ µN(Player 2 wins) = 1

lim

N→∞

PN(Player 1 wins) = lim

N→∞

PN(Player 2 wins) = 1

Finally, we establish that there exist natural ways to partition the collection of Zeckendorf

games ΩNon input Nso that the distribution of game lengths over the corresponding

classes are nearly Gaussian with high probability in the limit N→ ∞. The construction of

the subsets RP

N⊂ΩNand RS

N⊂ΩN, and the sets AN(R), is elaborated in Propositions 4.8

and 4.9.

Theorem 1.12. For R∈RP

N, let FR

N(x):R→[0,1] denote the distribution function

corresponding to game lengths in AN(R) over the conditional distribution induced by PN,

normalized to have expectation 0 and variance 1. Let Φ :R→[0,1] denote the distribution

function of the standard normal. Then for any  > 0,

lim

N→∞

PN sup

x∈RFR

N(x)−Φ(x)≥!= 0.

Similarly, for R∈RS

N, let FR

N(x):R→[0,1] denote the distribution function corresponding

to game lengths in AN(R) over the conditional distribution induced by PN, normalized to

have expectation 0 and variance 1. Then for any  > 0,

lim

N→∞

PN sup

x∈RFR

N(x)−Φ(x)≥!= 0.

The analogous results hold for the uniform measure µN.

2. Structural Results

In this section, we include some straightforward, but fundamental results concerning the

nature of the Zeckendorf game; some of these will be invoked in proofs of deeper theorems.

2.1. Combinatorial Observations. We begin by exploring some basic properties of the

Zeckendorf game, observable by studying deterministic subroutines of moves. The following

simple result mirrors techniques in [3]

Proposition 2.1. Consider any decomposition of Ninto a sum of (possibly non-distinct,

non-consecutive) Fibonacci numbers: this decomposition can be achieved via a sequence of

combine moves from the starting conﬁguration of the Zeckendorf game.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

TOWARDSTHEGAUSSIANITYOFRANDOMZECKENDORFGAMESJUSTINCHEIGH,GUILHERMEZEUSDANTASEMOURA,RYANJEONG,JACOBLEHMANNDUKE,WYATTMILGRIM,STEVENJ.MILLER,PRAKODNGAMLAMAIAbstract.Zeckendorfprovedthatanypositiveintegerhasauniquedecompositionasasumofnon-consecutiveFibonaccinumbers,indexedbyF1=1;F2=2;Fn+1=Fn+Fn1.Motiva...

展开>> 收起<<

TOWARDS THE GAUSSIANITY OF RANDOM ZECKENDORF GAMES JUSTIN CHEIGH GUILHERME ZEUS DANTAS E MOURA RYAN JEONG JACOB LEHMANN DUKE WYATT MILGRIM STEVEN J. MILLER PRAKOD NGAMLAMAI.pdf

共29页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

TOWARDS THE GAUSSIANITY OF RANDOM ZECKENDORF GAMES JUSTIN CHEIGH GUILHERME ZEUS DANTAS E MOURA RYAN JEONG JACOB LEHMANN DUKE WYATT MILGRIM STEVEN J. MILLER PRAKOD NGAMLAMAI

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: