# 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
$F_{1}=1,F_{2}=2,F_{n+1}=F_{n}+F_{n-1}$. Motivated by this result, Baird,
Epstein, Flint, and Miller [3] 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, [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\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 [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\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.

###### Contents

  1. 1 Introduction
    1. 1.1 Prior Work
    2. 1.2 Notation and Conventions
    3. 1.3 Main Results
  2. 2 Structural Results
    1. 2.1 Combinatorial Observations
    2. 2.2 Shortest Games
  3. 3 The Set of Possible Game Lengths Constitute An Interval
  4. 4 Winning Odds in the Limit $N\to\infty$
    1. 4.1 Overview
    2. 4.2 Partitioning the Collection of Possible Games
    3. 4.3 Analysis
    4. 4.4 Extending the Partition on $\Omega_{N}$
  5. 5 Weak Convergence of Random Game Lengths as $N\to\infty$
  6. 6 Open Problems
    1. 6.1 Other Two-Player Games Based on Recurrences
    2. 6.2 Towards Gaussianity: Other Approaches
    3. 6.3 Towards Gaussianity: Mixing

##  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 $F_{1}=1$, $F_{2}=2$, and for general $n\geq 3$,
$F_{n}=F_{n-1}+F_{n-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 $N$ can 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.

######  Definition 1.2 ([3]).

Given input $N\in\mathbb{N}$, the Zeckendorf game is played on a multiset of
Fibonacci numbers, initialized at $\mathcal{S}=\\{F_{1}^{N}\\}$. On each turn,
a player can act on the multiset by performing one of the following moves if
it is available.

  1. (1)

If we have two consecutive Fibonacci numbers $F_{k-1},F_{k}$ for some $k\geq
2$, then we can replace them by $F_{k+1}$, denoted $F_{k-1}\wedge F_{k}\to
F_{k+1}$.

  2. (2)

If we have two instances of the same Fibonacci number $F_{k}$, then

    1. (a)

If $k=1$, we can play $F_{1}\wedge F_{1}\to F_{2}$.

    2. (b)

If $k=2$, we can play $F_{2}\wedge F_{2}\to F_{1}\wedge F_{3}$.

    3. (c)

If $k\geq 3$, we can play $F_{k}\wedge F_{k}\to F_{k-2}\wedge F_{k+1}$.

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 $k$ corresponding to the Fibonacci number
$F_{k}$ and its height being the multiplicity of $F_{k}$ in 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\geq 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 $N$ is 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 fixed input $N$; the former article finds a
deterministic game which has longest possible length for input $N$, while the
latter generalizes this paradigm. We frequently 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, finding a convenient closed
form for the length of the longest game for non-Fibonacci input $N$ remains
open (with the case of Fibonacci input treated by [5]).

######  Theorem 1.4 ([5]).

The longest game on any $N$ is achieved by applying split moves or combine
$1$s (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 $N$ can be played with strictly splitting and
combine $1$ moves if and only if $N=F_{k}-1$ for some $k\geq 2$.

Finally, we remark that analogous two-player games have been developed for
other recurrences: the work [2] extends [3] by defining and studying such
games for recursive sequences defined by linear recurrence relations of form
$G_{n}=\sum_{i=1}^{k}cG_{n-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
$a_{n+1}=na_{n}+a_{n-1}$.

###  1.2. Notation and Conventions

We let $C_{1}$ denote the combine move $F_{1}\wedge F_{1}\to F_{2}$, and (for
$k\geq 2$) let $C_{k}$ denote the combine move $F_{k-1}\wedge F_{k}\to
F_{k+1}$. Let $S_{2}$ denote the splitting move $2F_{2}\to F_{1}\wedge F_{3}$,
and (for $k\geq 3$) let $S_{k}$ denote the splitting move $2F_{k}\to
F_{k-2}\wedge F_{k+1}$. We prefix a particular type of move with $M$ to denote
the number of such moves (e.g. $MC_{1}$ denotes the number of $C_{1}$’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 $F_{k}$ as the height of
bin $k$, denoted $h_{k}$; it will usually be clear from context at which point
in the game the quantity $h_{k}$ refers to. When discussing the height of bin
$k$ after a specific number $m$ of moves in the game, we notate this by
$h_{k}(m)$. For $\lambda\in\mathbb{N}$, we shall also occasionally use the
shorthand $[\lambda]=\\{1,2,\dots,\lambda\\}$.

In this work, we shall generally work under the assumption that $F_{n}\leq
N<F_{n+1}$ for some $n\in\mathbb{N}$ (i.e., $n$ is the index of the largest
Fibonacci number that is no larger than $N$)111This is why we have elected to
deviate from notation traditionally used in papers concerning this game..
While proving Theorem 1.9, we occasionally refer to moves
$C_{1},S_{2},\dots,S_{n-1}$ as Type A moves, and all other moves (namely,
moves $C_{k}$ for $k\geq 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 $\Omega_{N}$ denotes the (finite) collection of all Zeckendorf
games on input $N$, with $\mathcal{F}_{N}=2^{\Omega_{N}}$ the associated
$\sigma$-algebra, and express a given Zeckendorf game
$\mathcal{G}\in\Omega_{N}$ as a (finite) sequence of $\lambda$ moves, written
as $\mathcal{G}=(M_{1},M_{2},\dots,M_{\lambda})$. We study two probability
measures to complete the space $(\Omega_{N},\mathcal{F}_{N})$: the uniform
measure $\mu_{N}$, defined by

$\displaystyle\mu_{N}(\mathcal{G})=\frac{1}{|\Omega_{N}|}\text{ for all
}\mathcal{G}\in\Omega_{N}$

and the probability measure $\mathbb{P}_{N}$ induced by choosing, at every
configuration along a given game, uniformly at random among available moves,
defined by

$\displaystyle\mathbb{P}_{N}(\mathcal{G})=\prod_{k=1}^{\lambda}\frac{1}{\text{num.
playable moves after }(M_{1},\dots,M_{k-1})}\text{ for
}\mathcal{G}=(M_{1},M_{2},\dots,M_{\lambda})\in\Omega_{N}.$

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 $N$ is upper-bounded by

$\left\lfloor\varphi^{2}N-Z_{I}(N)-2Z(N)+(\varphi-1)\right\rfloor$

where $Z_{I}(N)$ represents the index sum of the Zeckendorf decomposition of
$N$. Furthermore, the bound is sharp for infinitely 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 $N$ in the limit $N\to\infty$.

######  Conjecture 1.7 ([3, 7]).

In the limit $N\to\infty$, the distribution of the number of moves in a random
Zeckendorf game on input $N$ converges to a Gaussian, with expectation and
variance approximately $0.215N$.222The 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\leq 18$ and found the distribution of lengths appeared
to be Gaussian. This is a slightly different problem than the random game
though is closely related.

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 conjecture (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
underestimate 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 $F_{n}\leq N<F_{n+1}$. Then the number of shortest Zeckendorf games with
input $N$ is at least $\prod_{k=1}^{n-2}\text{Cat}(F_{k})$, where
$\text{Cat}(F_{k})$ denotes the $F_{k}\textsuperscript{th}$ 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 affirmative.

######  Theorem 1.9.

For any input $N$ to the Zeckendorf game, let $M$ denote the length of the
longest Zeckendorf game with input $N$. Then for any $m$ satisfying
$N-Z(N)\leq m\leq M$, there exists a Zeckendorf game of length $m$ on 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\to\infty$ of
infinite 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 infinite
input, a $Z$-player random Zeckendorf game is fair, in the sense that all $Z$
players have the same probability of winning.

######  Theorem 1.10.

For any integer $Z\geq 1$ and $z\in\\{0,1,\dots,M-1\\}$, we have that

$\displaystyle\lim_{N\to\infty}\mu_{N}(\text{Game length equals }z\text{ mod
}Z)=\lim_{N\to\infty}\mathbb{P}_{N}(\text{Game length equals }z\text{ mod
}Z)=\frac{1}{Z}.$

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\to\infty$ under both
probability measures $\mu_{N}$ and $\mathbb{P}_{N}$, Player 1 and Player 2 are
equally likely to win. Explicitly,

$\displaystyle\lim_{N\to\infty}\mu_{N}(\text{Player 1
wins})=\lim_{N\to\infty}\mu_{N}(\text{Player 2 wins})=\frac{1}{2},$
$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}(\text{Player 1
wins})=\lim_{N\to\infty}\mathbb{P}_{N}(\text{Player 2 wins})=\frac{1}{2}.$

Finally, we establish that there exist natural ways to partition the
collection of Zeckendorf games $\Omega_{N}$ on input $N$ so that the
distribution of game lengths over the corresponding classes are nearly
Gaussian with high probability in the limit $N\to\infty$. The construction of
the subsets $\mathcal{R}_{N}^{\mathcal{P}}\subset\Omega_{N}$ and
$\mathcal{R}_{N}^{\mathcal{S}}\subset\Omega_{N}$, and the sets
$\mathcal{A}_{N}(\mathcal{R})$, is elaborated in Propositions 4.8 and 4.9.

######  Theorem 1.12.

For $\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$, let
$F_{N}^{\mathcal{R}}(x)\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to[0,1]$ denote the distribution function corresponding
to game lengths in $\mathcal{A}_{N}(\mathcal{R})$ over the conditional
distribution induced by $\mathbb{P}_{N}$, normalized to have expectation $0$
and variance $1$. Let $\Phi\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to[0,1]$ denote the distribution function of the standard
normal. Then for any $\epsilon>0$,

$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}\left(\sup_{x\in\mathbb{R}}\left|F_{N}^{\mathcal{R}}(x)-\Phi(x)\right|\geq\epsilon\right)=0.$

Similarly, for $\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{S}}$, let
$F_{N}^{\mathcal{R}}(x)\mathrel{\mathop{\mathchar
58\relax}}\mathbb{R}\to[0,1]$ denote the distribution function corresponding
to game lengths in $\mathcal{A}_{N}(\mathcal{R})$ over the conditional
distribution induced by $\mathbb{P}_{N}$, normalized to have expectation $0$
and variance $1$. Then for any $\epsilon>0$,

$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}\left(\sup_{x\in\mathbb{R}}\left|F_{N}^{\mathcal{R}}(x)-\Phi(x)\right|\geq\epsilon\right)=0.$

The analogous results hold for the uniform measure $\mu_{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 $N$ into a sum of (possibly non-distinct, non-
consecutive) Fibonacci numbers: this decomposition can be achieved via a
sequence of combine moves from the starting configuration of the Zeckendorf
game.

###### Proof.

We “play the game in reverse”: consider the configuration corresponding to
this decomposition, and construct a sequence of moves by always taking the
game piece not in the first bin (i.e., $F_{1}$) and farthest out, and replace
it as the result of a combine move. Specifically, if $k\geq 3$, then replace
$F_{k}$ by $\\{F_{k-2},F_{k-1}\\}$; if $k=2$, replace with $2F_{1}$. Then
reverse all the moves to get a Zeckendorf game from the initial state to this
state. ∎

The following is an easy consequence of Theorem 1.4 above, which states that
the longest game paradigm from the starting position extends to intermediate
game positions on input $N$ which are given by converting $F_{n}-1$ instances
of $F_{1}=1$ into the Zeckendorf decomposition of $F_{n}-1$, where $n$ denotes
the index of the largest Fibonacci number in the Zeckendorf decomposition of
the input $N$.

######  Lemma 2.2.

Let $n$ denote the index of the largest Fibonacci number in the Zeckendorf
decomposition of the input $N$. A longest Zeckendorf game from an intermediate
configuration given by converting $F_{n}-1$ instances of $1$ into the
Zeckendorf decomposition of $F_{n}-1$ is given by greedily playing any Type A
move whenever possible, and if no such Type A move can be played, play the
available Type B move with the smallest index.

###### Proof.

If a game achieved by playing Type A moves whenever possible from this
configuration were not maximal (i.e., there existed a Zeckendorf game of
strictly larger length), then by initially playing the longest game on input
$F_{n}-1$ via all Type A moves (possible by Theorem 1.5), we can play the game
exactly according to Theorem 1.4 but fail to achieve a game of maximal length,
contradicting Theorem 1.4. ∎

Using similar techniques as in [3], we derive the following results in order
to improve the upper bound found in [5].

######  Lemma 2.3.

Let $n$ be the largest summand in the Zeckendorf decomposition of $N$, we get
that for any $2\leq k\leq n-1$, the following sum is constant:

$MS_{k}+MC_{k}+MC_{k+1}+\cdots+MC_{n-1}.$

###### Proof.

Consider the following relabeling of the board:

$F_{1}$ | $\cdots$ | $F_{k}$ | $F_{k+1}-1$ | $F_{k+2}-2$ | $F_{k+3}-4$ | $F_{k+4}-7$ | $\cdots$
---|---|---|---|---|---|---|---

where after the $k\textsuperscript{th}$ bin, the value of a bin is equal to
one less than the sum of the values of the two bins which precede it. We get
that only the moves $S_{k},C_{k},C_{k+1},\dots$ can change the weighted sum of
the tokens by the relabeled values, and each of these moves reduce the sum by
1. Since we have a fixed initial sum $N$ and a fixed ending sum depending on
the Zeckendorf Decomposition of $N$, we get that the sum of those moves must
be constant regardless of how the game is played. ∎

######  Lemma 2.4.

For any Zeckendorf game starting with $N$ tokens,

$MC_{1}-MS_{2}\approx(2-\varphi)N$

with approximation error $\leq\varphi-1$.

###### Proof.

Similarly, we prove this with a relabeling of the board

$2$ | $3$ | $5$ | $\cdots$ | $F_{k+1}$ | $\cdots$
---|---|---|---|---|---

and observing that the sum of token values goes from $2N$ to $\sim\varphi N$
with the sum decreasing by 1 only by performing $C_{1}$ and increasing by 1
only by performing $S_{2}$. Note that the final sum is equal to shifting each
Zeckendorf summands of $N$ forward by one, which is approximated by
multiplying each by $\varphi$. By Binet’s formula, we have
$F_{k}=\frac{\varphi^{k+1}-(-1/\varphi)^{k+1}}{\sqrt{5}}$ due to how we index
the Fibonacci sequence. Thus, the error of approximating the summand $F_{k+1}$
with $\varphi F_{k}$ is

$\left\lvert\frac{(\varphi^{k+1}-(-1/\varphi)^{k+1})\varphi-(\varphi^{k+2}-(-1/\varphi)^{k+2})}{\sqrt{5}}\right\rvert=\frac{\varphi^{2}+1}{\varphi^{k+2}\sqrt{5}}$

The largest error happens when $N=F_{1}+F_{3}+F_{5}+\cdots$ with error at most

$\frac{\varphi^{2}+1}{\varphi^{3}\sqrt{5}}\left(\sum_{i=0}^{\infty}\frac{1}{\varphi^{2i}}\right)=\frac{\varphi^{2}+1}{\varphi^{3}(1-1/\varphi^{2})\sqrt{5}}=\frac{1}{\varphi}=\varphi-1$

which yields the desired. ∎

As a corollary, we prove Theorem 1.6. See 1.6

###### Proof.

Using the relabeling of the board given by

$3$ | $4$ | $5$ | $\cdots$ | $k+2$ | $\cdots$
---|---|---|---|---|---

we get that

$\displaystyle 2MC_{1}+2MC_{2}+3MC_{3}+4MC_{4}+$
$\displaystyle\cdots=3N-2Z(N)-Z_{I}(N)$ $\displaystyle+MS_{3}+MS_{4}+$
$\displaystyle\cdots$

Applying Lemma 2.4, we get

$\displaystyle MC_{1}+2MC_{2}+3MC_{3}+4MC_{4}+$ $\displaystyle\cdots\leq
3N-2Z(N)-Z_{I}(N)$
$\displaystyle+(2-\varphi)N-(\varphi-1)+MS_{2}+MS_{3}+MS_{4}+$
$\displaystyle\cdots$

Thus, if we subtract the excess $MC_{2}+2MC_{3}+3MC_{4}+\cdots$ from the left
hand side, we get the upper bound

$\displaystyle MC_{1}+MC_{2}+MC_{3}+MC_{4}+$
$\displaystyle\cdots\leq(1+\varphi)N-2Z(N)-Z_{I}(N)+(\varphi-1)$
$\displaystyle+MS_{2}+MS_{3}+MS_{4}+$ $\displaystyle\cdots$

which we round down as the number of all moves performed is an integer. Note
that if we consider $N=F_{n}-1$ then we get that there are no $C_{2},C_{3},$
performed within the longest game. Furthermore, if we consider $N=F_{2n}-1$,
then our approximation error is less than $1$ and thus must be sharp after
rounding down. ∎

Recall that [3] proved non-constructively that Player $2$ always has a winning
strategy for any $N\geq 3$: finding such a winning strategy remains open. It
is generally believed ([8]) that the key to such a strategy lies in
understanding “parity swaps”: distinct sequences of moves of differing length
which yield the same effect on the board. The following definition follows
from the easy observation that whenever playable, the sequences of moves

$\displaystyle S_{k}\to S_{k-1}\to\cdots\to S_{k-\ell+1}\to C_{k-\ell}$
$\displaystyle C_{k-\ell}\to S_{k-\ell+1}\to\cdots\to S_{k-1}\to S_{k}$

both have the same effect on the board as the move $C_{k}$, for some $k\geq
2$.

######  Definition 2.5.

For any $\ell\geq 0$ and $k\geq 2$, call a sequence of moves of form $S_{k}\to
S_{k-1}\to\cdots\to S_{k-\ell+1}\to C_{k-\ell}$ an $(\ell,k)$-prefix, and a
sequence of moves of form $C_{k-\ell}\to S_{k-\ell+1}\to
S_{k-\ell+2}\to\cdots\to S_{k}$ an $(\ell,k)$-suffix. We call an
$(\ell,k)$-prefix a prefix of $C_{k}$, and an $(\ell,k)$-suffix a suffix of
$C_{k}.$

It should be emphasized that an $(\ell,k)$-prefix or $(\ell,k)$-suffix
corresponds to an equivalent action as the combine move $C_{k}$, for all
lengths $\ell\geq 0$ and $k\geq 2$; the combine move is thus “expanded” via a
sequence of $\ell$ splitting moves with contiguous indices. The next result
captures the intuition that the variation in game lengths is entirely due to
the parity swaps described in Definition 2.5, namely by describing arbitrary
Zeckendorf games via permutations of suffixes.

######  Proposition 2.6.

Any Zeckendorf game on input $N$ can be achieved by taking a shortest game,
expanding combine moves via suffixes, then shifting the splitting moves.

###### Proof.

For an arbitrary Zeckendorf game, greedily take the earliest split move of a
game, move it back to be played as early as possible, and compress it into a
combine move. Proceed similarly until we only have combine moves, from which
we achieve the original game by reversing the compressions and playing split
moves later. ∎

We can interpret the statement of Proposition 2.6 as saying that we can
greedily embed an arbitrary Zeckendorf game on input $N$ into a shortest game
on input $N$ in a natural way.

###  2.2. Shortest Games

Proposition 2.6 suggests that a study of shortest Zeckendorf games might be
fruitful, as any particular Zeckendorf game can be understood as an extension
and permutation of a particular shortest game. We first observe the following.

######  Proposition 2.7.

Shortest games are exactly those games which strictly use combine moves.
Furthermore, such a game exists for any input $N$, and the multiset of combine
moves for any such shortest game is unique.

###### Proof.

A move decreases the number of pieces by at most one, so $N-Z(N)$ lower-bounds
the number of moves necessary, achieved exactly by those games using strictly
combine moves; such games exist by Proposition 2.1. To establish uniqueness of
the multiset of combine moves for any such game, say $F_{n}\leq N<F_{n+1}$,
and study bin $k$ for $1\leq k\leq n$. Moves affecting $h_{k}$ are known
precisely: letting the Zeckendorf decomposition of $N$ be denoted
$(z_{1},z_{2},\dots,z_{n})$ (where $z_{i}\in\\{0,1\\}$), this yields the
system

$\displaystyle N-2MC_{1}-MC_{2}$ $\displaystyle=z_{1}$ $\displaystyle
MC_{1}-MC_{2}-MC_{3}$ $\displaystyle=z_{2}$ $\displaystyle\cdots$
$\displaystyle MC_{n-3}-MC_{n-2}-MC_{n-1}$ $\displaystyle=z_{n-2}$
$\displaystyle MC_{n-2}-MC_{n-1}$ $\displaystyle=z_{n-1}$ $\displaystyle
MC_{n-1}$ $\displaystyle=z_{n}=1$

from which it easily follows that this system must have a unique solution. ∎

######  Proposition 2.8.

For $n=n(N)$ and any $\delta\in(0,1)$,

$\displaystyle\lim_{N\to\infty}\max_{\mathcal{G}\in\Omega_{N}}\frac{\\#\\{C_{k}\in\mathcal{G},k>\delta
n\\}}{\\#\\{\text{Combine moves in
}\mathcal{G}\\}}=\lim_{N\to\infty}\max_{\mathcal{G}\in\Omega_{N}}\frac{\\#\\{C_{k}\in\mathcal{G},k>\delta
n\\}}{N-1}=0.$

###### Proof.

For $\mathcal{G}\in\Omega_{N}$, consider all combine moves $C_{k}$ with
$k>\delta n$; each such combine move corresponds to a particular token
“jumped,” for which we consider all combine moves with index $\leq\delta n$
that led this token to land in this position, of which there must be at least
$\lfloor\delta n/2\rfloor$. The sets of combine moves with index $\leq\delta
n$ corresponding to distinct combine moves with index $>\delta n$ are observed
to be disjoint, so

$\displaystyle\frac{\\#\\{C_{k}\in\mathcal{G},k>\delta
n\\}}{N-1}\leq\frac{1}{\lfloor\delta n/2\rfloor+1}$

which vanishes as $N\to\infty$. ∎

Proposition 2.7 yields the following interesting lower bound333We suspect the
lower bound of Theorem 1.8 to be somewhat loose, as much is lost when crudely
pursuing the interweaving of the Dyck paths $\pi_{2},\pi_{3},\dots,\pi_{n-1}$
(see the proof for details). on the number of shortest Zeckendorf games with
input $N$. See 1.8

###### Proof.

It suffices to study $N=F_{n}$, since the number of distinct shortest
Zeckendorf games is increasing in $N$: for input $N\neq F_{n}$, one can first
play a shortest Zeckendorf game on input $F_{n}$, then proceed by always
playing the rightmost available combine move to achieve a shortest game on
input $N$ by Proposition 2.7. (See Lemma 3.1, where we understand this as
incrementing instances of $F_{1}$s after playing a shortest game on $F_{n}$.)
The Zeckendorf decomposition is
$(z_{1},z_{2},\dots,z_{n-1},z_{n})=(0,0,\dots,0,1)$, where $z_{i}$ denotes the
number of instances of $F_{i}$ in the decomposition. By Proposition 2.7, there
exists a unique multiset of combine moves constituting a shortest game: by
solving the system above, this multiset is defined by

$\displaystyle(MC_{1},MC_{2},\dots,MC_{n-1})=(F_{n-2},F_{n-3},F_{n-4},\dots,F_{3},F_{2},F_{1},F_{0})$

where we let $F_{0}=1$. A permutation of these moves constitutes a game if and
only if every move is valid, i.e., no move would force the height of any bin
to become negative. Specifically, at any intermediate point in the sequence,
the number of $C_{1}$’s played is no less than the sum of the number of
$C_{2}$’s and $C_{3}$’s played (bin $2$ is nonnegative), the number of
$C_{2}$’s is no less than the number of $C_{3}$’s and $C_{4}$’s played (bin
$3$ is nonnegative), and so on, to the number or $C_{n-2}$’s being no less
than the number of $C_{n-1}$’s played (bin $n-1$ is nonnegative). (We need not
study bin $1$ or bin $n$, which will necessarily always have nonnegative
height.)

Let us restrict our attention to the moves $C_{1},C_{2},C_{3}$ (moves
affecting the height of bin $2$): the number of permutations of these moves
such that the number of $C_{1}$’s played being no less than the sum of the
number of $C_{2}$’s and $C_{3}$’s performed holds at any point in the game is
in bijective correspondence with (up-down) Dyck paths on $j=F_{n-2}$
($C_{1}\leftrightarrow U$; $C_{2},C_{3}\leftrightarrow D$), the number of
which is $\text{Cat}(F_{n-2})$. Similarly, by studying moves affecting bin
$k\geq 2$, we achieve bijective correspondences with Dyck paths on
$j=F_{n-k}$.

For any choice of Dyck paths $\pi_{2},\pi_{3},\dots,\pi_{n-1}$ on
$j=F_{n-2},F_{n-3},\dots,F_{1}$, respectively, there exists a shortest
Zeckendorf game on input $N$ where the ordering of the relevant moves is
consistent with the bijections described above. To construct such a game,
begin by placing $2F_{n-2}$ moves along a line, labeling $F_{n-2}$ of them as
$C_{1}$ in a manner consistent with $\pi_{2}$ ($C_{1}\leftrightarrow U$).
Among the $F_{n-2}=F_{n-3}+F_{n-4}$ unlabeled moves, label $F_{n-3}$ of them
as $C_{2}$ (importantly, including the first $D$ move) in a manner consistent
with $\pi_{3}$ (not too many unlabeled moves between consecutive instances of
$C_{2}$) and the other $F_{n-4}$ as $C_{3}$. Now add $F_{n-5}$ instances of
$C_{4}$ along this line to complete $\pi_{3}$ (include all missing
$C_{4}\leftrightarrow D$ moves) while respecting $\pi_{4}$ (not too many
unlabeled moves between consecutive instances of $C_{3}$). Specifically,
construct a labeling of the $F_{n-3}=F_{n-4}+F_{n-5}$ $D$ moves in $\pi_{3}$
with $F_{n-4}$ $C_{3}$’s and $F_{n-5}$ $C_{4}$’s such that the first $D$ is
labeled $C_{3}$, and there are not too many unlabeled $D$ moves between
consecutive instances of $C_{3}$ (with respect to $\pi_{4}$). Insert $C_{4}$’s
to be adjacent to established instances of $C_{2}$ and $C_{3}$ to be
consistent with this labeling.

Continue by similarly adding, for $k\geq 5$, $F_{n-k-1}$ instances of $C_{k}$,
completing $\pi_{k-1}$ while respecting $\pi_{k}$, until we add $F_{0}=1$
instance of $C_{n-1}$ such that we complete $\pi_{n-1}$. This results in a
shortest Zeckendorf game with the ordering of the relevant moves being
consistent with $\pi_{2},\pi_{3},\dots,\pi_{n-1}$. ∎

##  3\. The Set of Possible Game Lengths Constitute An Interval

In this section, we prove Theorem 1.9, which we restate below.

See 1.9

We begin by establishing some intermediate results that we shall invoke in the
proof of the main theorem. In the first lemma, in discussing the position
given by the Zeckendorf decomposition of $N-1$, we refer to the terminal
position of the Zeckendorf game when played on input $N-1$.

######  Lemma 3.1.

Consider the Zeckendorf game on input $N$, satisfying $F_{n}\leq N<F_{n+1}$,
from the position given by the Zeckendorf decomposition on $N-1$ (as specified
above) with an additional instance of $1$. There is a unique sequence of moves
from this configuration to the Zeckendorf decomposition of $N$, all of which
are combine moves. Furthermore, the number of such combine moves performed is
bounded by $\lfloor n/2\rfloor$.

###### Proof.

Since no moves can be played from the Zeckendorf decomposition on $N-1$, any
playable move from this position (on input $N$) is necessarily either $C_{1}$
or $C_{2}$, possible if and only if $F_{1}=1$ or $F_{2}=2$ is in the
Zeckendorf decomposition of $N-1$, respectively (such cases are disjoint,
since the Zeckendorf decomposition on $N-1$ does not contain consecutive
Fibonacci numbers); otherwise, no moves can be played. We study both cases.

  * •

If the Zeckendorf decomposition of $N-1$ contains an instance of $F_{1}$, then
after playing $C_{1}$, it is easy to see that the only possible move is
$C_{3}$ (iff the decomposition of $N-1$ contains an $F_{3}$), then $C_{5}$
(iff the decomposition of $N-1$ contains an $F_{5}$), and so on, until we
exhaust all playable moves.

  * •

If the Zeckendorf decomposition of $N-1$ contains an instance of $F_{2}$, then
after playing $C_{2}$, it is easy to see that the only possible move is
$C_{4}$ (iff the decomposition of $N-1$ contains an $F_{4}$), then $C_{6}$
(iff the decomposition of $N-1$ contains an $F_{6}$), and so on, until we
exhaust all playable moves.

In both cases, it is straightforward to confirm that we cannot play strictly
more than $\lfloor n/2\rfloor$ such combine moves, as otherwise there must be
an instance of $F_{k}$ for $k$ either $n+1$ or $n+2$ after completing this
sequence of moves, a contradiction on $N<F_{n+1}$. ∎

We shall also frequently use the following lemma. Intuitively, this states
that if we have isolated the Zeckendorf game to a suffix of bins all of height
$0$ or $1$, and this suffix is separated from earlier bins by a bin of height
$0$ (say bin $k$), then we can ignore bins $1,\dots,k$ for the remainder of
the game.

######  Lemma 3.2.

For some $1\leq k\leq n$, let $(x_{1},x_{2},\dots,x_{k},x_{k+1},\dots,x_{n})$
denote the heights of bins $1,\dots,n$ at some point during a Zeckendorf game,
with $x_{i}$ denoting the height of bin $i$. Assume $x_{i}\in\\{0,1\\}$ for
$k\leq i\leq n$, $x_{k}=0$, no playable moves involving bins $1,\dots,k$
exist, and we play according to Theorem 1.4. Then heights $x_{1},\dots,x_{k}$
remain fixed for the rest of the game.

###### Proof.

We prove this on $k=n-j$ by induction on $0\leq j\leq n-2$. The statement
trivially holds if $j\in\\{0,1,2\\}$; assuming it for all values less than
$j\geq 3$, if $x_{k+1}=0$ or $x_{k+2}=0$ we can apply the induction hypothesis
to $j-1$ or $j-2$, respectively, so assume $x_{k+1}=x_{k+2}=1$. Take $r\leq n$
to be largest possible such that $x_{k+1}=\cdots=x_{r}=1$: the game proceeds
by playing according to Theorem 1.4, i.e., by playing the sequence of moves

$\displaystyle(C_{k+1}\to S_{k+3}\to S_{k+4}\to\cdots\to S_{r})\to(C_{k+1}\to
S_{k+3}\to\cdots\to S_{r-2})\to\cdots$

where the final subsequence of moves, either $C_{k+1}$ or $C_{k+1}\to
S_{k+3}$, depends on the parity of $r-k$. It follows immediately by studying
the moves involved that $x_{1},\dots,x_{k}$ remain unchanged during this
sequence. Following this sequence, we have $x_{r}=0$: invoke the induction
hypothesis on $k=r$ (i.e., $n-r<j$) afterwards to complete the proof. ∎

We now proceed with the proof of Theorem 1.9.

###### Proof of Theorem 1.9.

We have confirmed this statement for $N\leq F_{6}-1=12$ via a computer check.
Thus, for $N\geq F_{6}=13$, assume the statement holds for all input sizes at
most $N-1$: we aim to show the result holds for $N$. We explicitly specify
that $F_{n}\leq N<F_{n+1}$.

Let $I_{1}^{\prime}$ denote the interval (by induction hypothesis) of possible
Zeckendorf game lengths for input $N-1$: by Lemma 3.1, if we include an
additional instance of $F_{1}$ to the Zeckendorf decomposition of $N-1$, there
is a sequence of combine moves from the resulting configuration to the
Zeckendorf decomposition of $N$. On input $N$, consider initially playing the
Zeckendorf game (to completion) as if the input were $N-1$, then executing
this sequence of moves to terminate the game. Let $I_{1}=[L_{1},R_{1}]$ denote
the interval $I_{1}^{\prime}$ shifted by the length of this sequence: by the
preceding description, it follows that every game length in $I_{1}$ is
achievable for input $N$. Furthermore, $L_{1}=N-Z(N)$, since the game length
$L_{1}$ as studied above results from playing strictly combine moves (see
Lemma 3.1), which necessarily yields a shortest game by Proposition 2.7, and
for which the length is $N-Z(N)$ by Theorem 1.3.

By Theorem 1.5, it is possible to play the Zeckendorf game on input $F_{n}-1$
strictly using Type A moves. Let $I_{2}^{\prime}$ denote the interval (by
induction hypothesis) of possible Zeckendorf game lengths for input
$F_{n}-1\leq N-1$: on input $N$, consider initially playing the Zeckendorf
game (to completion) as if the input were $F_{n}-1$, then executing the
longest possible sequence of moves from the resulting position to terminate
the game. Let $I_{2}=[L_{2},R_{2}]$ denote the interval $I_{2}^{\prime}$
shifted by the number of moves of this longest sequence. By Theorem 1.4,
$R_{2}$ is necessarily the length of the longest Zeckendorf game on input $N$,
since the above approach is consistent with playing Type A moves whenever
possible.

Thus, it suffices to show that $L_{2}\leq R_{1}$ to complete the induction and
establish the theorem, as this yields that $I_{1}\cup I_{2}=[L_{1},R_{2}]$ is
an interval of achievable game lengths on input $N$, with the endpoints being
the shortest and longest possible game lengths for input $N$.

The known game with length $R_{1}$ corresponds to playing the longest game on
input $N-1$, then performing the unique sequence of combine moves to achieve
the Zeckendorf decomposition of $N$; by Theorems 1.4 and 1.5, we can take the
first phase of this game (longest game on input $N-1$) as playing the longest
game on input $F_{n}-1$, then playing the longest remaining game (on input
$N-1$). The known game with length $L_{2}$ corresponds to playing the shortest
game on input $F_{n}-1$, then playing the longest remaining game until we
achieve the Zeckendorf decomposition of $N$. By Lemma 2.2, we can take the
second phase of this game (playing the longest remaining game) as playing
consistent to Theorem 1.4 until achieving the Zeckendorf decomposition.

We henceforth denote these games with length $R_{1}$ and $L_{2}$ by
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, respectively, which we depict as
follows; “longest on $k$” indicates that during this phase, we think of the
game as being played on input $k$, and leaving the appropriate number of
instances of $F_{1}=1$ in the first bin fixed.

$\displaystyle\mathcal{G}_{1}\mathrel{\mathop{\mathchar
58\relax}}\left[(\text{Longest on }F_{n}-1)\to(\text{longest remaining on
}N-1)\right]\to(\text{combine moves on }N)$
$\displaystyle\mathcal{G}_{2}\mathrel{\mathop{\mathchar
58\relax}}(\text{Shortest on }F_{n}-1)\to(\text{longest remaining on }N)$

Denoting the difference between the lengths of the longest and shortest games
on input $F_{n}-1$ by $\ell(n)$, game $\mathcal{G}_{1}$ took exactly $\ell(n)$
more moves than game $\mathcal{G}_{2}$ on input $F_{n}-1$. However,
$\mathcal{G}_{2}$ may take longer afterwards to finish the game on input $N$:
we aim to show that the discrepancy in the game lengths after initially
playing on input $F_{n}-1$ is dominated by $\ell(n)$, from which we conclude
that $\mathcal{G}_{2}$ is no longer than $\mathcal{G}_{1}$, i.e., that
$L_{2}\leq R_{1}$. In particular, it certainly suffices to show that the first
two segments of $\mathcal{G}_{1}$ involve at least as many moves as the first
two segments of $\mathcal{G}_{2}$ to establish the result: this is how we
shall proceed.

By Theorem 1.4 and Lemma 2.2, we can choose how we would like to play a
longest game after playing the game on input $F_{n}-1$ (specifically, we can
fix an ordering on Type A moves which determines what we play when given
multiple Type A moves): until the two games diverge444We shall assume this
does happen, as otherwise the lengths of the second segments of
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are equal, and thus the inequality
$L_{2}\leq R_{1}$ is immediate., pursue a longest remaining game by always
playing the rightmost Type A move whenever a Type A move is playable.
Following this ordering on Type A moves, we study the first move on which
games $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ deviate. This move is
necessarily either $C_{1}$ or $C_{2}$ in game $\mathcal{G}_{2}$ (the move must
not have been playable in game $\mathcal{G}_{1}$, and thus must involve bin
$1$), and by the ordering on Type A moves established before, bins
$2,3,\dots,n$ are either $0$ or $1$ when it is played. We perform casework on
which move the two games deviate on.

Case 1: Move is $C_{1}$. In game $\mathcal{G}_{1}$, this configuration can be
represented by the vector $(1,x_{2},x_{3},\dots,x_{n})$, where
$x_{i}\in\\{0,1\\}$ for $i\geq 2$ denotes the height of the $i$th bin (the
first entry would be a $2$ for game $\mathcal{G}_{2}$). Let us first study the
setting $x_{2}=0$, and consider what happens after game $\mathcal{G}_{2}$
plays $C_{1}$. If $x_{3}=0$, then by Lemma 3.2 applied to $k=3$, both games
are consistent on bins $4,\dots,n$ so that game $\mathcal{G}_{2}$ takes one
more move than $\mathcal{G}_{1}$ to finish. Otherwise (i.e., $x_{3}=1$), Lemma
3.2 on $k=2$ yields that game $\mathcal{G}_{1}$ works strictly over bins
$3,\dots,n$, and Lemma 3.2 on $k=1$ yields that game $\mathcal{G}_{2}$ works
strictly over the bins $2,\dots,n$ (i.e., bin $1$ becomes irrelevant). Thus,
the resulting setting corresponds exactly to Case 2 over the $n-1$ bins
$2,\dots,n$; here, we have an upper bound of $n-1$ for the number of
additional moves $\mathcal{G}_{2}$ takes, for a total upper bound of
$(n-1)+1=n$ (with the $C_{1}$ in $\mathcal{G}_{2}$) for the number of
additional moves $\mathcal{G}_{2}$ takes.

Thus, assume $x_{2}=1$, and let position $k+1$, with $k\geq 2$, denote the
first index that is $0$. Study the length-$k$ prefix $(1,1,1,\dots,1)$ (in
game $\mathcal{G}_{1}$; first entry is $2$ in game $\mathcal{G}_{2}$) with no
zero entries; we can exactly describe how the two games proceed when playing
according to the longest game paradigm of Theorem 1.4.

  * •

Game $\mathcal{G}_{1}$: We play the sequence of moves

$\displaystyle(C_{2}\to S_{3}\to S_{4}\to\cdots\to S_{k})\to(C_{2}\to
S_{3}\to\cdots\to S_{k-2})\to\cdots$

continuing similarly until one of the first two bins is empty (so we cannot
play $C_{2}$). In general, shorten the contiguous $1$s down two indices and
repeat until one of the first two bins is empty (the bin which ends up empty
depends on the parity of $k$).

  * •

Game $\mathcal{G}_{2}$: We play the sequence of moves

$\displaystyle(C_{1})\to(S_{2})\to(S_{3}\to C_{1})\to(S_{4}\to
S_{2})\to\cdots$

continuing similarly until we play all splitting moves $S_{j}$ for $j\leq k$.
In general, when first playing $S_{j}$, we play the sequence $S_{j}\to
S_{j-2}\to\cdots$ (final move is $S_{2}$ or $C_{1}$, depending on parity of
$j$), and this continues until position $k$.

After these subroutines, it is straightforward to confirm that bin $k$ is
empty, bins $k+1,\dots,n-1$ are all $0$ or $1$ with heights agreeing between
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, and no playable moves involving bins
$1,\dots,k$ exist. Thus, both games proceed strictly over bins $k+1$ to $n-1$
by Lemma 3.2, and perform the same sequence of moves; we need only compute the
difference in the lengths of these two subroutines on this prefix of length
$k$.

  * •

The length of the sequence of moves in the game of length $L_{2}$ is

$\displaystyle\begin{cases}2\sum_{j=1}^{(k-1)/2}j+\frac{k+1}{2}&k\text{
odd,}\\\ 2\sum_{j=1}^{k/2}j&k\text{ even.}\end{cases}$

  * •

The length of the sequence of moves in the game of length $R_{1}$ is

$\displaystyle\begin{cases}\sum_{j=1}^{(k-1)/2}(k-2j+1)=2\sum_{j=1}^{(k-1)/2}j&k\text{
odd,}\\\
\sum_{j=1}^{k/2}(k-2j+1)=\sum_{j=1}^{k/2}(2j-1)=2(\sum_{j=1}^{k/2}j)-\frac{k}{2}&k\text{
even.}\end{cases}$

We can thus study this difference exactly: the difference is given by

$\displaystyle\begin{cases}\left[2\sum_{j=1}^{(k-1)/2}j+\frac{k+1}{2}\right]-2\sum_{j=1}^{(k-1)/2}j=\frac{k+1}{2}=\lceil
k/2\rceil&k\text{ odd}\\\
2\sum_{j=1}^{k/2}j-\sum_{j=1}^{k/2}(2j-1)=\frac{k}{2}&k\text{
even}\end{cases}$

so in general, the difference is bounded by $\lceil n/2\rceil\leq n$.

Case 2: Move is $C_{2}$. In game $\mathcal{G}_{1}$, this configuration can be
represented by the vector $(0,x_{2},x_{3},\dots,x_{n})$, where
$x_{i}\in\\{0,1\\}$ for $i\geq 2$ denotes the height of the $i$th bin (the
first entry would be a $1$ for game $\mathcal{G}_{2}$) and $x_{2}=1$ (since
otherwise $C_{2}$ cannot be played in game $\mathcal{G}_{2}$). Let us first
study the setting $x_{3}=0$, and consider what happens after game
$\mathcal{G}_{2}$ plays $C_{2}$. Applying Lemma 3.2 on $k=3$ for
$\mathcal{G}_{1}$ and $k=2$ for $\mathcal{G}_{2}$ yield that both games work
strictly over bins $3,\dots,n$, and this reduces to the same setting on the
suffix of bins $3,\dots,n$. Say we reduce the problem to a suffix with length
reduced by $2$ in this manner $m$ times, so we study the case where $x_{3}=1$
over $n-2m$ bins: by extracting the bound in the following argument (i.e., the
$x_{3}=1$ case) for the number of additional moves $\mathcal{G}_{2}$ takes,
this yields a bound of $m+(n-2m)\leq n$.

Thus, assume $x_{3}=1$, and let position $k+1$, with $k\geq 3$, denote the
first index that is $0$. Study the length-$k$ prefix $(0,1,1,\dots,1)$ (in
game $\mathcal{G}_{1}$; first entry is $1$ in game $\mathcal{G}_{2}$): we can
explicitly describe how the two games necessarily proceed when playing
according to the longest game paradigm.

  * •

Game $\mathcal{G}_{1}$: We play the sequence of moves

$\displaystyle(C_{3}\to S_{4}\to S_{5}\to\cdots\to S_{k})\to(C_{3}\to
S_{4}\to\cdots\to S_{k-2})\to\cdots$

continuing similarly until either bin $2$ or bin $3$ is empty (so we cannot
play $C_{3}$). In general, shorten the contiguous $1$s down two indices and
repeat until either bin $2$ or bin $3$ is empty (the bin which ends up empty
depends on the parity of $k$).

  * •

Game $\mathcal{G}_{2}$: This is exactly the same as game $\mathcal{G}_{1}$ in
Case 1.

After these subroutines, it is straightforward to confirm that bin $k$ is
empty, bins $k+1,\dots,n-1$ are all $0$ or $1$ with heights agreeing between
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$, and no playable moves involving bins
$1,\dots,k$ exist. Thus, both games proceed strictly over bins $k+1$ to $n-1$
by Lemma 3.2, and perform the same sequence of moves; we need only compute the
difference in the lengths of these two subroutines on this prefix of length
$k$.

The length of the sequence of moves in game $\mathcal{G}_{2}$ was computed in
Case 1, while the length of the sequence of moves in game $\mathcal{G}_{1}$ is

$\displaystyle\begin{cases}\sum_{j=1}^{(k-1)/2}(k-2j)=\sum_{j=1}^{(k-1)/2}(2j-1)=2(\sum_{j=1}^{(k-1)/2}j)-\frac{k-1}{2}&k\text{
odd}\\\
\sum_{j=1}^{(k-2)/2}(k-2j)=\sum_{j=1}^{(k-2)/2}(2j-1)=2(\sum_{j=1}^{(k-2)/2}j)-\frac{k-2}{2}&k\text{
even.}\end{cases}$

so the difference is given by

$\displaystyle\begin{cases}2\sum_{j=1}^{(k-1)/2}j-\left[2(\sum_{j=1}^{(k-1)/2}j)-\frac{k-1}{2}\right]=\frac{k-1}{2}=\lfloor
k/2\rfloor&k\text{ odd}\\\
\left[2(\sum_{j=1}^{k/2}j)-\frac{k}{2}\right]-\left[2(\sum_{j=1}^{(k-2)/2}j)-\frac{k-2}{2}\right]=k-1&k\text{
even}\end{cases}$

so in general, the difference is bounded by $\max\\{\lfloor
k/2\rfloor,k-1\\}\leq n-1\leq n$.

We observe that in both cases, the difference in the lengths of the second
segments of these games is bounded by $n$. We now show that the difference
$\ell(n)$ between the lengths of the longest and shortest games on input
$F_{n}-1$ is at least $n$ for all $n\geq 6$. One can confirm, by playing a
longest game according to Theorem 1.4 on input $N=F_{6}-1=12$, that
$\ell(6)=17-(12-Z(12))=17-9\geq 6$; it is similarly easy to confirm that
$\ell(4),\ell(5)\geq 1$. Since we have
$F_{n+1}-1=(F_{n}-1)+F_{n-1}\geq(F_{n}-1)+(F_{n-1}-1)$, one can pursue a game
on input $F_{n+1}-1$ by first playing a game on input $F_{n}-1$, then a game
on input $F_{n-1}-1$, and finally performing some fixed sequence of moves to
completion. By combining respective shortest games and longest games on input
$F_{n}-1$ and input $F_{n-1}-1$, we observe that $\ell(n+1)-\ell(n)\geq 1$ for
any $n\geq 6$, and thus $\ell(n)\geq n$ for all $n\geq 6$ (recall $\ell(6)\geq
6$).

Therefore, we have that for all $N\geq F_{6}=13$,

$\displaystyle R_{1}-L_{2}$ $\displaystyle\geq\ell(n)-\left[(\text{len.
longest remaining on $N$})-(\text{len. longest remaining on $N-1$})\right]$
$\displaystyle\geq\ell(n)-n\geq\ell(n)-\ell(n)=0$

from which we conclude that $L_{2}\leq R_{1}$. ∎

##  4\. Winning Odds in the Limit $N\to\infty$

We dedicate this section to establishing Theorem 1.11, which follows as an
immediate corollary of Theorem 1.10: recall that Theorem 1.10 is given as
follows. See 1.10 The case $Z=2$ gives Theorem 1.11. See 1.11

###  4.1. Overview

We provide a brief sketch of the proof of Theorem 1.11. We specifically focus
on the number of $(1,k)$-prefixes which occur over the course of a game,
recalling that whenever applicable, the sequence of moves $(S_{k},C_{k-1})$
has the same effect on the game as $C_{k}$. We partition the collection of
games $\Omega_{N}$ into subsets of games which differ only via such
$(1,k)$-prefixes, describe the conditional distribution induced by any such
subset (under both $\mu_{N}$ and $\mathbb{P}_{N}$), and argue that in the
limit of infinite input, the sizes of the subsets induced by this partition
grow so fast that the probability of Player 1 or Player 2 winning can be
reduced to the outcome of a binomial random variable with exploding variance.

###  4.2. Partitioning the Collection of Possible Games

As observed in Definition 2.5, for $k\geq 2$, the sequence555We deviate from
notation earlier in the paper and write move sequences as tuples.
$(S_{k},C_{k-1})$ is a $(1,k)$-prefix. We establish some notation to use
later: define $\mathcal{R}_{N}\in\mathcal{F}_{N}$ to be the collection666We
elect to use the notation $\mathcal{R}_{N}$ as we think of these games on
input $N$ as representatives of the corresponding classes
$\mathcal{A}_{N}(\mathcal{R})$ that we define later in this discussion. of all
Zeckendorf games on input $N$ such that (for all $k\geq 2$) any instance of
the sequence $(S_{k},C_{k-1})$ is immediately preceded by $S_{k+1}$; in other
words, $\mathcal{R}_{N}$ is the collection of all Zeckendorf games on input
$N$ such that there are no $(1,k)$-prefixes for any $k\geq 2$. We can express
this collection as

$\displaystyle\mathcal{R}_{N}=\left\\{(M_{1},\dots,M_{\lambda})\in\Omega_{N}\mathrel{\mathop{\mathchar
58\relax}}(M_{i},M_{i+1})=(S_{k},C_{k-1})\implies M_{i-1}=S_{k+1}\ \forall\
i\in[\lambda-1],k\geq 2\right\\}.$

For a game $\mathcal{R}=(M_{1},M_{2},\dots,M_{\lambda})\in\mathcal{R}_{N}$,
construct the subset of indices $\mathcal{I}_{N}(\mathcal{R})$ to denote all
combine moves in $\mathcal{R}$, not involved in a sequence $(S_{k},C_{k-1})$
for $k\geq 2$, for which the latter bin has height at least $2$ (i.e., combine
moves $C_{k}$ for $k\geq 2$ replaceable with a $(1,k)$-prefix):

$\displaystyle\mathcal{I}_{N}(\mathcal{R})=\left\\{i\in[\lambda]\mathrel{\mathop{\mathchar
58\relax}}M_{i}=C_{k},\ M_{i-1}\neq S_{k+1},\ h_{k}(i)\geq 2\text{ for some
}k\geq 2\right\\}.$

Now, construct the formal sequence of moves
$\mathcal{M}(\mathcal{R})=(\tilde{M}_{1},\tilde{M}_{2},\dots,\tilde{M}_{\lambda})$
by replacing $M_{i}$ by a symbol $\mathcal{E}_{k}$ (the subscript being the
corresponding $k\geq 2$) for all $i\in\mathcal{I}_{N}(\mathcal{R})$; call
$\mathcal{M}(\mathcal{R})$ the base sequence of
$\mathcal{R}\in\mathcal{R}_{N}$. Let
$\mathcal{A}_{N}(\mathcal{R})\in\mathcal{F}_{N}$ denote the collection of all
Zeckendorf games resulting from replacing each instance of $\mathcal{E}_{k}$
in $\mathcal{M}$ by either $C_{k}$ or the $1$-prefix $(S_{k},C_{k-1})$ (for
every $k\geq 2$). We establish the following important result, which makes it
clear why we have pursued this construction in the manner that we did.

######  Lemma 4.1.

The sets $\\{\mathcal{A}_{N}(\mathcal{R})\mathrel{\mathop{\mathchar
58\relax}}\mathcal{R}\in\mathcal{R}_{N}\\}$ partition $\Omega_{N}$.

###### Proof.

We first show that the sets $\mathcal{A}_{N}(\mathcal{R})$ are disjoint. Take
distinct
$\mathcal{R}_{1}=(M_{1}^{1},\dots,M_{\lambda}^{1}),\mathcal{R}_{2}=(M_{1}^{2},\dots,M_{\lambda^{\prime}}^{2})\in\mathcal{R}_{N}$
with base sequences
$\mathcal{M}_{1}(\mathcal{R}_{1})=(\tilde{M}_{1}^{1},\tilde{M}_{2}^{1},\dots,\tilde{M}_{\lambda}^{1})$
and
$\mathcal{M}_{2}(\mathcal{R}_{2})=(\tilde{M}_{1}^{2},\tilde{M}_{2}^{2},\dots,\tilde{M}_{\lambda^{\prime}}^{2})$,
respectively. Since $\mathcal{R}_{1}\neq\mathcal{R}_{2}$, take smallest $i$
for which $M_{i}^{1}\neq
M_{i}^{2}\implies\tilde{M}_{i}^{1}\neq\tilde{M}_{i}^{2}$, and study the
construction of any two games
$\mathcal{G}_{1}\in\mathcal{A}_{N}(\mathcal{R}_{1})$ and
$\mathcal{G}_{2}\in\mathcal{A}_{N}(\mathcal{R}_{2})$ as described above. If
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are consistent prior to
$\tilde{M}_{i}^{1}$ and $\tilde{M}_{i}^{2}$ (i.e., for $k\geq 2$, all
$\mathcal{E}_{k}$ are replaced by the same choice of $C_{k}$ or
$(S_{k},C_{k-1})$), which is certainly the only way the two games remain equal
up to this point of their construction, then we necessarily produce a
difference in the two games on $\tilde{M}_{i}^{1}$ and $\tilde{M}_{i}^{2}$ if
$M_{i}^{1}=\tilde{M}_{i}^{1}$ and $M_{i}^{2}=\tilde{M}_{i}^{2}$
($M_{i}^{1}\neq M_{i}^{2}$) or $M_{i}^{1}\neq\tilde{M}_{i}^{1}$ and
$M_{i}^{2}\neq\tilde{M}_{i}^{2}$ ($\tilde{M}_{i}^{1}=\mathcal{E}_{k_{1}}$,
$\tilde{M}_{i}^{2}=\mathcal{E}_{k_{2}}$, $k_{1}\neq k_{2}$). If
$M_{i}^{1}=\tilde{M}_{i}^{1}$ and $M_{i}^{2}\neq\tilde{M}_{i}^{2}$ (say
$\tilde{M}_{i}^{2}=\mathcal{E}_{k}$, so necessarily $M_{i}^{2}=C_{k}$ and
$M_{i-1}^{2}\neq S_{k+1}$ for some $k\geq 2$), then game $\mathcal{G}_{2}$ is
next filled with either $C_{k}\neq M_{i}^{1}$ ($M_{i}^{1}=M_{i}^{2}$ if
$C_{k}=M_{i}^{1}$) or $(S_{k},C_{k-1})$. In the latter case, if the two games
were equal after this, then necessarily
$(M_{i-1}^{1},M_{i}^{1},M_{i+1}^{1})=(S_{k+1},S_{k},C_{k-1})$ (by definition
of $\mathcal{I}_{N}(\mathcal{R}_{1})$ and $\mathcal{R}_{N}$, $M_{i+1}^{1}$ and
$M_{i-1}^{1}$ follow after establishing $M_{i}^{1}=S_{k}$), contradicting
$M_{i-1}^{2}\neq S_{k+1}$ (since $M_{i-1}^{1}=M_{i-1}^{2}$ and
$M_{i}^{2}=C_{k}$, $\tilde{M}_{i}^{2}=\mathcal{E}_{k}$).

We therefore conclude that
$\mathcal{A}_{N}(\mathcal{R}_{1})\cap\mathcal{A}_{N}(\mathcal{R}_{2})=\emptyset$,
i.e., the sets $\mathcal{A}_{N}(\mathcal{R})$ for
$\mathcal{R}\in\mathcal{R}_{N}$ are disjoint; it remains to show that any game
$\mathcal{G}\in\Omega_{N}$ is in some set $\mathcal{A}_{N}(\mathcal{R})$. For
$\mathcal{G}\in\Omega_{N}$, let $\mathcal{R}$ be the game resulting from
replacing every instance of the sequence $(M,S_{k},C_{k-1})$, $M\neq S_{k+1}$
in game $\mathcal{G}$ by the sequence $(M,C_{k})$ (for $k\geq 2$). The
resulting game $\mathcal{R}$ is such that
$(M_{i},M_{i+1})=(S_{k},C_{k-1})\implies M_{i-1}=S_{k+1}$ for all
$i\in[\lambda]$ and $k\geq 2$: any sequence
$(M_{i-1},M_{i},M_{i+1})=(M,S_{k},C_{k-1})$ with $M\neq S_{k+1}$ in
$\mathcal{R}$ necessarily results from having replaced $(S_{k-1},C_{k-2})$ for
$C_{k-1}$ in game $\mathcal{G}$ (as $(S_{k},C_{k-1})$ would have been replaced
by $S_{k+1}$ otherwise), but we know this does not occur by the description
above, so we indeed have $\mathcal{R}\in\mathcal{R}_{N}$. Also,
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$: we can reverse all the
replacements $(S_{k},C_{k-1})\leftrightarrow C_{k}$ made in achieving
$\mathcal{R}$ from $\mathcal{G}$, since the resulting $C_{k}$ moves correspond
to $\mathcal{E}_{k}$ (for some $k\geq 2$) in the base sequence
$\mathcal{M}(\mathcal{R})$ as the preceding move is not $S_{k+1}$. ∎

Therefore, applying Lemma 4.1 and the law of total probability,

$\displaystyle\mu_{N}(\text{Game length is }z\text{ mod
}Z)=\sum_{\mathcal{R}\in\mathcal{R}_{N}}\mu_{N}\left(\text{Game length is
}z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\mu_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)$
(1) $\displaystyle\mathbb{P}_{N}(\text{Game length is }z\text{ mod
}Z)=\sum_{\mathcal{R}\in\mathcal{R}_{N}}\mathbb{P}_{N}\left(\text{Game length
is }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)$

so we can reduce proving Theorem 1.10 to establishing that the conditional
probabilities for $\mathcal{R}\in\mathcal{R}_{N}$, with respect to both
measures, overwhelmingly tend to $1/2$ in the limit.

###  4.3. Analysis

Define the random variable $m_{N}\mathrel{\mathop{\mathchar
58\relax}}\Omega_{N}\to\mathbb{N}$ first on $\mathcal{R}\in\mathcal{R}_{N}$ by
$m_{N}(\mathcal{R})=|\mathcal{I}_{N}(\mathcal{R})|$, denoting the number of
terms $\mathcal{E}_{k}$ (for $k\geq 2$) in the base sequence of $\mathcal{R}$,
then lift to arbitrary $\mathcal{G}\in\Omega_{N}$ by letting
$m_{N}(\mathcal{G})=m_{N}(\mathcal{R})$ for the unique
$\mathcal{R}\in\mathcal{R}_{N}$ such that
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$ (see Lemma 4.1).777In particular,
$m_{N}(\mathcal{R})=\log_{2}(\mathcal{A}_{N}(\mathcal{R}))$. Fix
$\mathcal{R}\in\mathcal{R}_{N}$, and observe that on the event
$\mathcal{A}_{N}(\mathcal{R})$, $m_{N}(\mathcal{G})$ for
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$ is the fixed constant
$|\mathcal{I}_{N}(\mathcal{R})|$. Now construct corresponding Bernoulli random
variables
$X_{1}^{\mathcal{R}},X_{2}^{\mathcal{R}},\dots,X_{|m_{N}(\mathcal{R})|}^{\mathcal{R}}\mathrel{\mathop{\mathchar
58\relax}}\Omega_{N}\to\\{0,1\\}$ for each of the instances of terms of form
$\mathcal{E}_{k}$ (for $k\geq 2$) in the base sequence of $\mathcal{R}$: here,
$X_{i}^{\mathcal{R}}(\mathcal{G})=1$ if and only if
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$ and $\mathcal{G}$ is achieved by
the $i$th instance of $\mathcal{E}_{k}$ in the base sequence $\mathcal{R}$
being the $(1,k)$-prefix $(S_{k},C_{k-1})$. Say we replaced this
$\mathcal{E}_{k}$ with $(S_{k},C_{k-1})$, and let $n_{i}$ denote the number of
playable moves in the game available in the turn immediately after playing
$S_{k}$. We can say more about the random variables $X_{i}^{\mathcal{R}}$
defined here.

######  Lemma 4.2.

Fix some $\mathcal{R}\in\mathcal{R}_{N}$, and define the random variables
$X_{1}^{\mathcal{R}},X_{2}^{\mathcal{R}},\dots,X_{|m_{N}(\mathcal{R})|}^{\mathcal{R}}$
as above. When conditioned on $\mathcal{A}_{N}(\mathcal{R})$, the random
variables
$X_{1}^{\mathcal{R}},X_{2}^{\mathcal{R}},\dots,X_{|m_{N}(\mathcal{R})|}^{\mathcal{R}}$
are independent Bernoulli random variables with variable $X_{i}^{\mathcal{R}}$
having parameter $1/2$ under the measure $\mu_{N}$, and parameter
$p_{i}=\frac{1}{1+n_{i}}$ under the measure $\mathbb{P}_{N}$. Explicitly,

$\displaystyle\mu_{N}\left(X_{i}^{\mathcal{R}}=1\ |\
\mathcal{A}_{N}(\mathcal{R})\right)=\frac{1}{2},$
$\displaystyle\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\ |\
\mathcal{A}_{N}(\mathcal{R})\right)=\frac{1}{1+n_{i}}.$

###### Proof.

Fix a random variable $X_{i}^{\mathcal{R}}$, and observe that for every
particular setting of all other $\mathcal{E}_{k}$ terms in $\mathcal{R}$,
there exist exactly two games in $\mathcal{A}_{N}(\mathcal{R})$ faithful to
this setting, corresponding to choosing $C_{k}$ and the $(1,k)$-prefix
$(S_{k},C_{k-1})$ for the $i$th such $\mathcal{E}_{k}$. It follows immediately
that under the uniform measure $\mu_{N}$, we indeed have
$\mu_{N}\left(X_{i}^{\mathcal{R}}=1\ |\
\mathcal{A}_{N}(\mathcal{R})\right)=\frac{1}{2}$, since in particular there
exists a bijection between games in the subset $\mathcal{A}_{N}(\mathcal{R})$
with $X_{i}^{\mathcal{R}}=0$ and $X_{i}^{\mathcal{R}}=1$ and all games in
$\Omega_{N}$ are given equal probability under the measure $\mu_{N}$.

Under the probability measure $\mathbb{P}_{N}$, it is straightforward to
observe that the game replacing the $i$th instance of $\mathcal{E}_{k}$ by the
$(1,k)$-prefix $(S_{k},C_{k-1})$ requires an additional decision with
probability $\frac{1}{n_{i}}$ of yielding the desired $C_{k-1}$, and it thus
follows that the parameter $p_{i}$ of the Bernoulli random variable
$X_{i}^{\mathcal{R}}$ is given by

$\displaystyle\frac{p_{i}}{1-p_{i}}=\frac{1}{n_{i}}\implies
p_{i}=\frac{1}{1+n_{i}}.$

To establish independence, it suffices to show that for any subset
$S\subseteq\left[m_{N}(\mathcal{R})\right]$, we have the identity

$\displaystyle\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\text{ iff }i\in S\ |\
\mathcal{A}_{N}(\mathcal{R})\right)$ $\displaystyle=\prod_{i\in
S}\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\prod_{j\notin
S}\mathbb{P}_{N}\left(X_{j}^{\mathcal{R}}=0\ |\
\mathcal{A}_{N}(\mathcal{R})\right)$ $\displaystyle=\prod_{i\in
S}p_{i}\cdot\prod_{j\notin S}(1-p_{j}).$

We can relate the conditional probabilities
$\left\\{\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\text{ iff }i\in S\ \
\mathcal{A}_{N}(\mathcal{R})\right)\mathrel{\mathop{\mathchar
58\relax}}S\in\left[m_{N}(\mathcal{R})\right]\right\\}$ whenever
$S_{1}=S_{2}\cup\\{j\\}$ (for $j\in\left[m_{N}(\mathcal{R})\right]$): all
choices for each term $\mathcal{E}_{k}$ but one are consistent (namely,
$X_{j}^{\mathcal{R}}=1$ for the numerator in the following), and thus

$\displaystyle\frac{\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\text{ iff }i\in
S_{1}\ |\
\mathcal{A}_{N}(\mathcal{R})\right)}{\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\text{
iff }i\in S_{2}\ |\
\mathcal{A}_{N}(\mathcal{R})\right)}=\frac{1}{n_{j}}=\frac{p_{j}}{1-p_{j}}=\frac{\prod_{i\in
S_{1}}p_{i}\cdot\prod_{j\notin S_{1}}(1-p_{j})}{\prod_{i\in
S_{2}}p_{i}\cdot\prod_{j\notin S_{2}}(1-p_{j})}.$

Now, since we have the identity

$\displaystyle\sum_{S\subseteq\left[m_{N}(\mathcal{R})\right]}\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\text{
iff }i\in S\ |\ \mathcal{A}_{N}(\mathcal{R})\right)$
$\displaystyle=1=\prod_{i=1}^{m_{N}(\mathcal{R})}\left(p_{i}+(1-p_{i})\right)$
$\displaystyle=\sum_{S\subseteq\left[m_{N}(\mathcal{R})\right]}\left(\prod_{i\in
S}p_{i}\cdot\prod_{j\notin S}(1-p_{j})\right)$

and quotients between summands corresponding to two sets differing by one
element are the same, the summands on both sides for any subset
$S\subseteq\left[m_{N}(\mathcal{R})\right]$ are necessarily equal. More
specifically, letting $p_{1}=\mathbb{P}_{N}\left(X_{i}^{\mathcal{R}}=1\text{
iff }i\in\emptyset\ |\ \mathcal{A}_{N}(\mathcal{R})\right)$ and
$p_{2}=\prod_{i\in\emptyset}p_{i}\cdot\prod_{j\notin\emptyset}(1-p_{j})$, by
incrementally including elements to some
$S\subseteq\left[m_{N}(\mathcal{R})\right]$ we can write the corresponding
summands on the left and right hand sides as the same multiple of $p_{1}$ and
$p_{2}$, respectively. This reduces to $p_{1}=p_{2}$, and thus summands
corresponding to the same $S$ are equal. Thus, we have the desired identity
for any subset $S\subseteq\left[m_{N}(\mathcal{R})\right]$. ∎

Lemma 4.2 yields the following easy observation.

######  Corollary 4.3.

Say $F_{n}\leq N<F_{n+1}$, fix some $\mathcal{R}\in\mathcal{R}_{N}$, and
define the random variables
$X_{1}^{\mathcal{R}},X_{2}^{\mathcal{R}},\dots,X_{m_{N}(\mathcal{R})}^{\mathcal{R}}$
as above. Under the uniform measure $\mu_{N}$, whenever
$\mathcal{R}\in\mathcal{R}_{N}$ is such that $m_{N}(\mathcal{R})>0$,
$\mu_{N}\left(\text{Player 1 wins}\ |\
\mathcal{A}_{N}(\mathcal{R})\right)=1/2$. Under the probability measure
$\mathbb{P}_{N}$, when conditioned on the event
$\mathcal{A}_{N}(\mathcal{R})$, there are at most $2n$ distinct values of the
parameters $p_{i}=\frac{1}{1+n_{i}}$ amongst the random variables
$X_{i}^{\mathcal{R}}$, and for any such $i$, $\frac{1}{2n-2}\leq p_{i}\leq
1/2$.

###### Proof.

If $m_{N}(\mathcal{R})>0$, then the statement $\mu_{N}\left(\text{Player 1
wins}\ |\ \mathcal{A}_{N}(\mathcal{R})\right)=1/2$ follows immediately by
applying the law of total probability on all settings of the Bernoulli random
variables
$(X_{2}^{\mathcal{R}},\dots,X_{m_{N}(\mathcal{R})}^{\mathcal{R}})\in\\{0,1\\}^{m_{N}(\mathcal{R})-1}$,
namely since this further conditioning always yields a conditional probability
of $1/2$ (see the proof of Lemma 4.2). At any point of a game
$\mathcal{G}\in\Omega_{N}$ satisfying $F_{n}\leq N<F_{n+1}$, there are at most
$2n-3$ (and thus certainly at most $2n$) playable moves (and thus at most
$2n-3$ distinct values of $n_{i}$, and thus $p_{i}$): the combine moves
$C_{1},C_{2},\dots,C_{n-1}$ and the splitting moves
$S_{2},S_{3},\dots,S_{n-1}$. In particular, since $n_{i}\in[2n-3]$ for all
$i\in\left[m_{N}(\mathcal{R})\right]$, it follows that $\frac{1}{1+(2n-3)}\leq
p_{i}\leq\frac{1}{1+1}$, i.e., $\frac{1}{2n-2}\leq p_{i}\leq\frac{1}{2}$. ∎

We will also make use of the following lemma.

######  Lemma 4.4.

Say $F_{n}\leq N<F_{n+1}$.888It is perhaps more appropriate to think of $n$ as
a function $n(N)$. For any $c\in(0,\varphi)$ (with $\varphi$ denoting the
golden ratio),

$\displaystyle\lim_{N\to\infty}\mu_{N}\left(m_{N}(\mathcal{G})\geq
c^{n}\right)=1,$
$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}\left(m_{N}(\mathcal{G})\geq
c^{n}\right)=1.$

###### Proof.

Fix $c\in(0,\varphi)$, and consider a game $\mathcal{G}\in\Omega_{N}$: for the
representative $\mathcal{R}\in\mathcal{R}_{N}$ such that
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$, every occurrence of the sequence
$(C_{1},C_{1},C_{2})$ corresponds to an element of
$\mathcal{I}_{N}(\mathcal{R})$ (specifically the move $C_{2}$, as it is not
preceded by $S_{3}$, and the latter two moves are maintained in $\mathcal{R}$;
see the proof of Lemma 4.1), i.e.,
$m_{N}(\mathcal{G})=|\mathcal{I}_{N}(\mathcal{R})|$ is at least the number of
occurrences of the sequence $(C_{1},C_{1},C_{2})$ in $\mathcal{G}$. Letting
$\mathcal{N}(\mathcal{G})$ denote the number of occurrences of the sequence
$(C_{1},C_{1},C_{2})$ in the game $\mathcal{G}$, it thus suffices to show that

$\displaystyle\lim_{N\to\infty}\mu_{N}\left(\mathcal{N}(\mathcal{G})\geq
c^{n}\right)=1,$
$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}\left(\mathcal{N}(\mathcal{G})\geq
c^{n}\right)=1.$

Proceed studying the probability measure $\mathbb{P}_{N}$; the analysis
carries over exactly999Certainly, the analysis is much looser than necessary
when $\mathbb{P}_{N}$ is replaced with $\mu_{N}$. when $\mathbb{P}_{N}$ is
replaced with $\mu_{N}$. By Corollary 4.3, at any move where $h_{1}\geq 5$,
the probability of achieving the sequence $(C_{1},C_{1},C_{2})$ is at least
$\left(\frac{1}{2n}\right)^{3}=\frac{1}{8n^{3}}$, and any sequence of three
moves can decrease the height of bin $1$ by at most $6$ (via three consecutive
$C_{1}$ moves); observe that the occurrence of $C_{2}$ in a sequence
$(C_{1},C_{1},C_{2})$ within a game $\mathcal{G}$ necessarily corresponds to
an instance of the delimiter $\mathcal{E}_{2}$ in the base sequence of
$\mathcal{G}$ (e.g. see the proof of Lemma 4.1). Thus, study the sequences of
moves in game $\mathcal{G}$ (which necessarily exist by the preceding
discussion) given by the triples

$\displaystyle(M_{1},M_{2},M_{3}),(M_{4},M_{5},M_{6}),\dots,(M_{3\lfloor
N/6\rfloor-2},M_{3\lfloor N/6\rfloor-1},M_{3\lfloor N/6\rfloor})$

each of which independently takes on the value $(C_{1},C_{1},C_{2})$ with
probability at least $\frac{1}{8n^{3}}$. Thus, letting
$Y_{N}\stackrel{{\scriptstyle d}}{{=}}\text{Bin}\left(\lfloor
N/6\rfloor,p=\frac{1}{8n^{3}}\right)$, we have that

$\displaystyle\mathbb{P}\left(Y_{N}\geq
c^{n}\right)\leq\mathbb{P}_{N}\left(\mathcal{N}(\mathcal{G})\geq c^{n}\right)$

from which $\mathbb{E}[Y_{N}]=\frac{\lfloor N/6\rfloor}{8n^{3}}$ together with
a Chernoff bound with $\delta=\frac{1}{2}$ yields for $N$ large,

$\displaystyle\mathbb{P}\left(Y_{N}\leq
c^{n}\right)\leq\mathbb{P}\left(Y_{N}\leq\frac{\lfloor
N/6\rfloor}{16n^{3}}\right)\leq\exp\left(-\frac{\lfloor
N/6\rfloor}{32n^{3}}\right)\xrightarrow{N\to\infty}0$

since it is straightforward to verify that $c^{n}\leq\frac{\lfloor
N/6\rfloor}{16n^{3}}$ for large $N$ (e.g. use Binet). ∎

######  Corollary 4.5.

Lemma 4.4 immediately yields that for any $d\in\mathbb{N}$,

$\displaystyle\lim_{N\to\infty}\mu_{N}\left(m_{N}(\mathcal{G})\geq
n^{d}\right)=1,$
$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}\left(m_{N}(\mathcal{G})\geq
n^{d}\right)=1$

i.e., with probability approaching $1$ as $N\to\infty$, the number of
decisions made to achieve $\mathcal{G}$ from the set
$\mathcal{A}_{N}(\mathcal{R})$ containing it is superpolynomial in $n$. This
is more convenient for later.

The proof of Lemma 4.4 yields the following observations on the likeliest
collection $\mathcal{A}_{N}(\mathcal{R})$ and the number of representative
games, which will be referenced again in Section 5.

######  Corollary 4.6.

The probability of the likeliest collection $\mathcal{A}_{N}(\mathcal{R})$
vanishes as $N\to\infty$, i.e.,

$\displaystyle\lim_{N\to\infty}\max_{\mathcal{G}\in\Omega_{N}}\mu_{N}(\mathcal{A}_{N}(\mathcal{G}))=\lim_{N\to\infty}\max_{\mathcal{G}\in\Omega_{N}}\mathbb{P}_{N}(\mathcal{A}_{N}(\mathcal{G}))=0$

and the number of representatives satisfies
$|\mathcal{R}_{N}|\xrightarrow{N\to\infty}\infty$.

###### Proof.

Again, proceed on the probability measure $\mathbb{P}_{N}$, as the analysis
carries over exactly for $\mu_{N}$. The proof of Lemma 4.5 (taking $d=1$)
determines there are at least $m\geq n$ instances of $(C_{1},C_{1},C_{2})$ in
the first $\lfloor N/6\rfloor$ moves of a random game
$\mathcal{G}\in\Omega_{N}$, with probability tending to $1$ in the limit
$N\to\infty$: we proceed studying such a game $\mathcal{G}$. Writing
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$, every latter instance of $C_{1}$
in one of these $m$ sequences is in101010This is in the sense that this
instance of $C_{1}$ is not compressed in achieving $\mathcal{R}$ from
$\mathcal{G}$ (see the proof of Lemma 4.1), and is not replaced with a term of
form $\mathcal{E}_{k}$ in achieving the base sequence
$\mathcal{M}(\mathcal{R})$. any game in $\mathcal{A}_{N}(\mathcal{R})$, and
the move $C_{2}$ could have been played instead of this instance of $C_{1}$.
For $i=1,\dots,m$, denote
$\mathcal{B}_{i}^{N}(\mathcal{R})\subseteq\Omega_{N}$ to be those games
consistent with a game in $\mathcal{A}_{N}(\mathcal{R})$ up to the $i$th such
instance of $C_{1}$, but for which the move $C_{2}$ is played instead. It is
immediately observed that the sets $\mathcal{B}_{i}^{N}(\mathcal{R})$ are
disjoint and that
$\mathbb{P}_{N}(\mathcal{A}_{N}(\mathcal{R}))\leq\mathbb{P}_{N}(\mathcal{B}_{i}^{N}(\mathcal{R}))$
for each $i=1,\dots,m$, so we have

$\displaystyle n\cdot\mathbb{P}_{N}(\mathcal{A}_{N}(\mathcal{R}))\leq
m\cdot\mathbb{P}_{N}(\mathcal{A}_{N}(\mathcal{R}))\leq\sum_{i=1}^{m}\mathbb{P}_{N}(\mathcal{B}_{i}^{N}(\mathcal{R}))\leq
1\implies\mathbb{P}_{N}(\mathcal{A}_{N}(\mathcal{R}))\leq\frac{1}{n}\xrightarrow{N\to\infty}0$

so we have
$\lim_{N\to\infty}\max_{\mathcal{G}\in\Omega_{N}}\mathbb{P}_{N}(\mathcal{A}_{N}(\mathcal{G}))=0$,
and $|\mathcal{R}_{N}|\xrightarrow{N\to\infty}\infty$ follows immediately. ∎

Finally, we need the following simple result concerning the behavior of a
binomial random variable with sufficiently large variance. Certainly, the case
$Z=2$ in Lemma 4.7 corresponds to studying the expressions
$\mathbb{P}\left(\mathcal{B}\text{ is odd}\right)$ and
$\mathbb{P}\left(\mathcal{B}\text{ is even}\right)$.

######  Lemma 4.7.

Consider a binomial random variable $\mathcal{B}=\text{Bin}(m,p)$. For any
values of $\epsilon>0$ and $Z\in\mathbb{N}$, there exists a constant
$N(\epsilon,Z)$ such that if $\text{var}(\mathcal{B})=mp(1-p)\geq
N(\epsilon,Z)$ (i.e., if the variance of $\mathcal{B}$ is sufficiently large),
then for any $z\in\\{0,1,\dots,Z-1\\}$,

$\displaystyle\left|\mathbb{P}\left(\mathcal{B}\equiv z\text{ mod
}Z\right)-\frac{1}{Z}\right|\leq\epsilon.$

###### Proof.

The value $\mathbb{P}(\mathcal{B}=k)$ increases on $k\leq\lfloor(m+1)p\rfloor$
and decreases on $k\geq\lfloor(m+1)p\rfloor$, and $\max_{0\leq k\leq
m}\mathbb{P}(\mathcal{B}=k)=\mathbb{P}\left(\mathcal{B}=\lfloor(m+1)p\rfloor\right)\xrightarrow{mp(1-p)\to\infty}0$
(use Stirling); denoting $p_{k}=\mathbb{P}(\mathcal{B}=k)$, write $p_{0}\leq
p_{1}\leq\cdots\leq p_{\lfloor(m+1)p\rfloor}$ and
$p_{\lfloor(m+1)p\rfloor}\geq p_{\lfloor(m+1)p\rfloor+1}\geq\cdots\geq p_{m}$.
Fix $\epsilon>0$, and choose $N(\epsilon,Z)$ such that $mp(1-p)\geq
N(\epsilon,Z)$ implies
$\mathbb{P}\left(\mathcal{B}=\lfloor(m+1)p\rfloor\right)<\frac{\epsilon}{2}$.
Certainly, for any distinct values $z_{1}<z_{2}$ in $\\{0,1,\dots,Z-1\\}$, the
number of terms $p_{0},p_{1},\dots,p_{\lfloor(m+1)p\rfloor}$ with indices
equal to $z_{1}$ modulo $Z$ and equal to $z_{2}$ modulo $Z$ is either the same
or there exists one more such term corresponding to $z_{1}$: we can switch the
“dominant modulus” by removing the term of largest index equal to either
$z_{1}$ or $z_{2}$ modulo $Z$, for which the corresponding term
$p_{k}\leq\frac{\epsilon}{2}$ by choice of the constant $N(\epsilon,Z)$. The
analogous statement extends to
$p_{\lfloor(m+1)p\rfloor},p_{\lfloor(m+1)p\rfloor+1},\dots,p_{m}$, so it
follows that we can write

$\displaystyle\left|\mathbb{P}\left(\mathcal{B}\equiv z_{1}\text{ mod
}Z\right)-\mathbb{P}\left(\mathcal{B}\equiv z_{2}\text{ mod
}Z\right)\right|\leq\epsilon$

which immediately yields the desired statement. ∎

We are now ready to proceed with the proof of Theorem 1.10.

###### Proof of Theorem 1.10.

Fix an integer $Z\geq 2$ corresponding to the number of players in a
$Z$-player Zeckendorf game, and some value $z\in\\{0,1,\dots,Z-1\\}$. As in
the proof of Lemma 4.4, we strictly concern ourselves with the probability
measure $\mathbb{P}_{N}$, as the analysis carries over exactly for the uniform
measure $\mu_{N}$ (again, it is much looser than necessary for $\mu_{N}$). For
the probability measure $\mathbb{P}_{N}$, since $m_{N}(\mathcal{G})$ is fixed
at $|\mathcal{I}_{N}(\mathcal{R})|=m_{N}(\mathcal{R})$ on any set
$\mathcal{A}_{N}(\mathcal{R})$ for $\mathcal{R}\in\mathcal{R}_{N}$, for $N\geq
N_{1}(\epsilon)$,

(2)
$\displaystyle\mathop{\sum_{\mathcal{R}\in\mathcal{R}_{N}}}_{m_{N}(\mathcal{R})<2n^{3}}\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)\leq\epsilon.$

Consider a fixed representative $\mathcal{R}\in\mathcal{R}_{N}$ for which
$m_{N}(\mathcal{R})\geq 2n^{3}$: by Corollary 4.3, there are at most $2n$
distinct values of the parameters $p_{i}=\frac{1}{1+n_{i}}$ of the
corresponding random variables
$X_{1}^{\mathcal{R}},X_{2}^{\mathcal{R}},\dots,X_{m_{N}(\mathcal{R})}^{\mathcal{R}}$,
and thus by the pigeonhole principle, the number of instances of the value of
$p_{i}$ with largest multiplicity is at least
$\frac{2n^{3}}{2n}=n^{2}\xrightarrow{N\to\infty}\infty$; henceforth call this
$p$. Let us say there are $m\geq n^{2}$ instances of this value of $p_{i}$: we
can study the sum $\mathcal{B}_{\mathcal{R}}=\sum_{i=1}^{m}Y_{i}$, where the
$Y_{i}$ correspond to those random variables $X_{i}^{\mathcal{R}}$ with this
corresponding success probability $p$. Furthermore, by Lemma 4.2, the random
variables $Y_{i}$ are independent when conditioned on the event
$\mathcal{A}_{N}(\mathcal{R})$, so
$\mathcal{B}_{\mathcal{R}}\stackrel{{\scriptstyle d}}{{=}}\text{Bin}(m,p)$
under this conditional distribution. From the bounds on $p$ from Corollary
4.3, it follows that the variance of this binomial random variable, when
conditioned on the event $\mathcal{A}_{N}(\mathcal{R})$, has the exploding
lower bound

$\displaystyle\text{var}(\mathcal{B}_{\mathcal{R}})=mp(1-p)\geq\frac{n^{2}}{2(2n-2)}\xrightarrow{N\to\infty}\infty$

i.e., the binomial random variable $\mathcal{B}_{\mathcal{R}}$ has variance
exploding in the limit $N\to\infty$ (for any $\mathcal{R}\in\mathcal{R}_{N}$).
By Lemma 4.7, the random variable $\mathcal{B}_{\mathcal{R}}$ will take a
value equal to $z$ modulo $Z$ with probability approaching $\frac{1}{Z}$ as
$N\to\infty$. Thus, studying the quantities given by
$\mathbb{P}_{N}\left(\text{Game length equals }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)$, we can further condition (upon the
conditioning $\mathcal{A}_{N}(\mathcal{R})$) on all random variables
$X_{i}^{\mathcal{R}}$ not corresponding to those $Y_{i}$ constituting a
summand in the binomial random variable $\mathcal{B}_{\mathcal{R}}$ and appeal
to the law of total probability:

$\displaystyle\mathbb{P}_{N}\left(\text{Game length equals }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)$
$\displaystyle=\mathop{\sum_{\text{assignments }A}}_{\text{to
}X_{i}^{\mathcal{R}}\neq Y_{j}\forall j}\mathbb{P}_{N}\left(\text{Game length
equals }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R}),A\right)\cdot\mathbb{P}_{N}\left(A\ |\
\mathcal{A}_{N}(\mathcal{R})\right)$

where each term $\mathbb{P}_{N}\left(\text{Game length equals }z\text{ mod }Z\
|\ \mathcal{A}_{N}(\mathcal{R}),A\right)$ is understood as the probability
that the length of the game is equal to $z$ mod $Z$ when replacing those
$\mathcal{E}_{k}$ which correspond to the random variables $Y_{i}$, while
leaving all other moves of the game fixed: this is precisely given by the
binomial random variable $\mathcal{B}_{\mathcal{R}}$ added to some fixed
length determined by the setting of the $X_{i}^{\mathcal{R}}$ which are not of
the form $Y_{j}$ for some $j$. Letting $\ell(A)$ denote this length for the
assignment $A$, we can thus write

$\displaystyle\mathbb{P}_{N}\left(\text{Game length equals }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R}),A\right)=\mathbb{P}_{N}\left(\mathcal{B}_{\mathcal{R}}+\ell(A)\text{
is odd}\ |\ \mathcal{A}_{N}(\mathcal{R}),A\right).$

By Lemma 4.2, the random variables $Y_{i}$ constituting the Bernoulli trials
in $\mathcal{B}_{\mathcal{R}}$ are independent from the random variables
$X_{i}^{\mathcal{R}}$ that were fixed when conditioned on
$\mathcal{A}_{N}(\mathcal{R})$ and the assignment $A$, and thus we can apply
Lemma 4.7 to deduce that these conditional probabilities are arbitrarily close
to $\frac{1}{Z}$ for $N\geq N_{2}(\epsilon,Z)$ by the preceding discussion
(for sufficiently large $N_{2}(\epsilon,Z)\in\mathbb{N}$). Importantly, this
is uniform over all such terms in the sum, in the sense that we can choose
$N_{2}(\epsilon,Z)$ such that we achieve the same guarantee for any such
assignment $A$ of binary values to the random variables $X_{i}^{\mathcal{R}}$
not constituting $\mathcal{B}_{\mathcal{R}}$. Thus, for any
$\mathcal{R}\in\mathcal{R}_{N}$ satisfying $m_{N}(\mathcal{R})\geq 2n^{3}$ and
$N\geq N_{2}(\epsilon,Z)$, we have the bound

$\displaystyle\left|\mathbb{P}_{N}\left(\text{Game length equals }z\text{ mod
}Z\ |\ \mathcal{A}_{N}(\mathcal{R})\right)-\frac{1}{Z}\right|\leq\epsilon.$

Therefore, for $N\geq\max\\{N_{1}(\epsilon),N_{2}(\epsilon,Z)\\}$, we can take
Equations (4.2) and (2) to achieve the bound on the probability
$\mathbb{P}_{N}(\text{Game length equals }z\text{ mod }Z)$ given by

$\displaystyle\mathbb{P}_{N}(\text{Game length is }z\text{ mod
}Z)=\sum_{\mathcal{R}\in\mathcal{R}_{N}}\mathbb{P}_{N}\left(\text{Game length
is }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)$
$\displaystyle\leq\epsilon+\mathop{\sum_{\mathcal{R}\in\mathcal{R}_{N}}}_{m_{N}(\mathcal{R})\geq
2n^{3}}\mathbb{P}_{N}\left(\text{Game length is }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)$
$\displaystyle\leq\epsilon+\mathop{\sum_{\mathcal{R}\in\mathcal{R}_{N}}}_{m_{N}(\mathcal{R})\geq
2n^{3}}\left(\frac{1}{Z}+\epsilon\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)+\epsilon\leq\frac{1}{Z}+2\epsilon$

and similarly, we have

$\displaystyle\mathbb{P}_{N}(\text{Game length is }z\text{ mod
}Z)=\sum_{\mathcal{R}\in\mathcal{R}_{N}}\mathbb{P}_{N}\left(\text{Game length
is }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)$
$\displaystyle\geq\mathop{\sum_{\mathcal{R}\in\mathcal{R}_{N}}}_{m_{N}(\mathcal{R})\geq
2n^{3}}\mathbb{P}_{N}\left(\text{Game length is }z\text{ mod }Z\ |\
\mathcal{A}_{N}(\mathcal{R})\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)$
$\displaystyle\geq\mathop{\sum_{\mathcal{R}\in\mathcal{R}_{N}}}_{m_{N}(\mathcal{R})\geq
2n^{3}}\left(\frac{1}{Z}-\epsilon\right)\cdot\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)\geq\left(\frac{1}{Z}-\epsilon\right)(1-\epsilon)$

so we conclude that for $N\geq\max\\{N_{1}(\epsilon),N_{2}(\epsilon,Z)\\}$,

$\displaystyle\epsilon^{2}-\frac{Z+1}{Z}\epsilon\leq\mathbb{P}_{N}\left(\text{Game
length equals }z\text{ mod }Z\right)-\frac{1}{Z}\leq 2\epsilon$

which yields the desired limit by sending $\epsilon\downarrow 0$. ∎

As previously mentioned, the $Z=2$ case of Theorem 1.10 immediately yields
Theorem 1.11.

###  4.4. Extending the Partition on $\Omega_{N}$

Theorem 1.11 establishes that if both players advance randomly, the two-player
Zeckendorf game is fair in the limit $N\to\infty$: a key stage of the proof
involved partitioning $\Omega_{N}$ into collections of games where the games
in any given collection only differ via certain interchanges of
$(1,k)$-prefixes with the corresponding $C_{k}$. We can naturally extend this
partition of $\Omega_{N}$ (i.e., strictly larger classes in the partition) to
encompass arbitrary $(\ell,k)$-prefixes or arbitrary $(\ell,k)$-suffixes.
Section 5 will establish that for these enlarged partitions of $\Omega_{N}$,
we can achieve an analogue of 1.7 for the resulting sets in the partition, in
the sense that with high probability in the limit, the corresponding
distribution is “nearly Gaussian,” in the sense of vanishing Kolmogorov-
Smirnov distance (when mean and variance are normalized to be $0$ and $1$,
respectively) with the standard normal.111111In this subsection and Section 5,
we borrow much of the same notation that was used in establishing Theorem
1.11. It will be clear from context exactly what objects we are referring to.

We first study the generalization for arbitrary $(\ell,k)$-prefixes. Define
$\mathcal{R}_{N}^{\mathcal{P}}\in\mathcal{F}_{N}$ to be the collection of all
Zeckendorf games on input $N$ such that any combine move $C_{k}$, for $k\geq
2$, cannot be compressed by a $(1,k)$-prefix (and thus by any prefix of
$C_{k}$). Explicitly,

$\displaystyle\mathcal{R}_{N}^{\mathcal{P}}=\left\\{(M_{1},\dots,M_{\lambda})\in\Omega_{N}\mathrel{\mathop{\mathchar
58\relax}}M_{i}=C_{k}\implies M_{i-1}\neq S_{k+1}\text{ for all
}i\in[\lambda],k\geq 2\right\\}.$

For a game
$\mathcal{R}=(M_{1},M_{2},\dots,M_{\lambda})\in\mathcal{R}_{N}^{\mathcal{P}}$
with number of moves $\lambda$, construct the subset of indices
$\mathcal{I}_{N}(\mathcal{R})$ to denote all combine moves in $\mathcal{R}$:

$\displaystyle\mathcal{I}_{N}(\mathcal{R})=\left\\{i\in[\lambda]\mathrel{\mathop{\mathchar
58\relax}}M_{i}=C_{k}\text{ for some }k\geq 2\right\\}.$

Now, construct the formal sequence of moves
$\mathcal{M}(\mathcal{R})=(\tilde{M}_{1},\tilde{M}_{2},\dots,\tilde{M}_{\lambda})$
by replacing $M_{i}$ by a symbol $\mathcal{E}_{k}^{\ell}$ for all
$i\in\mathcal{I}_{N}(\mathcal{R})$: the subscript is the corresponding $k\geq
2$, while $\ell\geq 0$ denotes the longest $(\ell,k)$-prefix that
$M_{i}=C_{k}$ can be expanded into; note in particular that
$\mathcal{M}(\mathcal{R})$ contains no combine moves. Call
$\mathcal{M}(\mathcal{R})$ the base sequence of
$\mathcal{R}\in\mathcal{R}_{N}$, and let
$\mathcal{A}_{N}(\mathcal{R})\in\mathcal{F}_{N}$ denote the collection of all
Zeckendorf games resulting from replacing each instance of
$\mathcal{E}_{k}^{\ell}$ in $\mathcal{M}$ by an $(l,k)$-prefix for some
$l\leq\ell$. We establish the following analogue of Lemma 4.1, which yields a
strictly broader partition of $\Omega_{N}$ (in the sense that each set in the
partition given by Lemma 4.8 is a union of sets in the partition given by
Lemma 4.1).

######  Proposition 4.8.

The sets $\\{\mathcal{A}_{N}(\mathcal{R})\mathrel{\mathop{\mathchar
58\relax}}\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}\\}$ partition
$\Omega_{N}$.

###### Proof.

Observe that a base sequence
$\mathcal{M}(\mathcal{R})=(\tilde{M}_{1},\tilde{M}_{2},\dots,\tilde{M}_{\lambda})$
uniquely determines $\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$ by its
explicit split moves moves and the subscripts of each of its symbols
$\mathcal{E}_{k}^{\ell}$. This is true up to any initial subsequence, in the
sense that there exists at most one
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$ which agrees with the moves and
symbols $\mathcal{E}_{k}^{\ell}$ up to subscript.

We show that the sets $\mathcal{A}_{N}(\mathcal{R})$ are disjoint. Take
distinct
$\mathcal{R}_{1}=(M_{1}^{1},\dots,M_{\lambda}^{1}),\mathcal{R}_{2}=(M_{1}^{2},\dots,M_{\lambda^{\prime}}^{2})\in\mathcal{R}_{N}^{\mathcal{P}}$
with base sequences
$\mathcal{M}_{1}(\mathcal{R}_{1})=(\tilde{M}_{1}^{1},\tilde{M}_{2}^{1},\dots,\tilde{M}_{\lambda}^{1})$
and
$\mathcal{M}_{2}(\mathcal{R}_{2})=(\tilde{M}_{1}^{2},\tilde{M}_{2}^{2},\dots,\tilde{M}_{\lambda^{\prime}}^{2})$,
respectively. Since $\mathcal{R}_{1}\neq\mathcal{R}_{2}$, take smallest $i$
for which $M_{i}^{1}\neq M_{i}^{2}$, and study the construction of any two
games $\mathcal{G}_{1}\in\mathcal{A}_{N}(\mathcal{R}_{1})$ and
$\mathcal{G}_{2}\in\mathcal{A}_{N}(\mathcal{R}_{2})$ as described above. If
$\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ are consistent prior to
$\tilde{M}_{i}^{1}$ and $\tilde{M}_{i}^{2}$ (i.e., for $k\geq 2$, all
$\mathcal{E}_{k}^{\ell}$ are replaced by the same prefix of $C_{k}$), which is
the only way the two games remain equal up to this point, then we produce a
difference in the two games on $\tilde{M}_{i}^{1}$ and $\tilde{M}_{i}^{2}$ if
$M_{i}^{1}=\tilde{M}_{i}^{1}$ and $M_{i}^{2}=\tilde{M}_{i}^{2}$
($M_{i}^{1}\neq M_{i}^{2}$) or $M_{i}^{1}\neq\tilde{M}_{i}^{1}$ and
$M_{i}^{2}\neq\tilde{M}_{i}^{2}$
($\tilde{M}_{i}^{1}=\mathcal{E}_{k_{1}}^{\ell_{1}}$,
$\tilde{M}_{i}^{2}=\mathcal{E}_{k_{2}}^{\ell_{2}}$, $k_{1}\neq k_{2}$). If
$M_{i}^{1}=\tilde{M}_{i}^{1}$ and $M_{i}^{2}\neq\tilde{M}_{i}^{2}$ (say
$\tilde{M}_{i}^{2}=\mathcal{E}_{k}^{\ell}$, so $M_{i}^{2}=C_{k}$), then
$\mathcal{G}_{2}$ is next filled with either $C_{k}\neq M_{i}^{1}$
($M_{i}^{1}=M_{i}^{2}$ if $C_{k}=M_{i}^{1}$) or an $(l,k)$-prefix for some
$l\leq\ell$. In the latter case, if the two games were equal until move
$i+l-1$, necessarily $\mathcal{R}_{1}$ contains a prefix of length at least
$1$, contradicting $\mathcal{R}_{1}\in\mathcal{R}_{N}^{\mathcal{P}}$.

We therefore conclude that
$\mathcal{A}_{N}(\mathcal{R}_{1})\cap\mathcal{A}_{N}(\mathcal{R}_{2})=\emptyset$,
i.e., the sets $\mathcal{A}_{N}(\mathcal{R})$ for
$\mathcal{R}\in\mathcal{R}_{N}$ are disjoint; it remains to show that any game
$\mathcal{G}\in\Omega_{N}$ is in some set $\mathcal{A}_{N}(\mathcal{R})$. For
$\mathcal{G}\in\Omega_{N}$, let $\mathcal{R}$ be the game resulting from
replacing every combine move $C_{k}$ with the longest playable
$(\ell,k)$-prefix. It follows immediately from construction that
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$, and that
$\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$. ∎

Similarly, we define the generalization for arbitrary $(\ell,k)$-suffixes.
Define $\mathcal{R}_{N}^{\mathcal{S}}\in\mathcal{F}_{N}$ to be the collection
of all Zeckendorf games on input $N$ such that any combine move $C_{k}$, for
$k\geq 2$, cannot be compressed by a $(1,k)$-suffix (and thus by any suffix of
$C_{k}$). Explicitly,

$\displaystyle\mathcal{R}_{N}^{\mathcal{S}}=\left\\{(M_{1},\dots,M_{\lambda})\in\Omega_{N}\mathrel{\mathop{\mathchar
58\relax}}M_{i}=C_{k}\implies M_{i+1}\neq S_{k+1}\text{ for all
}i\in[\lambda],k\geq 2\right\\}.$

For a game
$\mathcal{R}=(M_{1},M_{2},\dots,M_{\lambda})\in\mathcal{R}_{N}^{\mathcal{S}}$
with number of moves $\lambda$, construct the subset of indices
$\mathcal{I}_{N}(\mathcal{R})$ to denote all combine moves in $\mathcal{R}$:

$\displaystyle\mathcal{I}_{N}(\mathcal{R})=\left\\{i\in[\lambda]\mathrel{\mathop{\mathchar
58\relax}}M_{i}=C_{k}\text{ for some }k\geq 2\right\\}.$

Now, construct the formal sequence of moves
$\mathcal{M}(\mathcal{R})=(\tilde{M}_{1},\tilde{M}_{2},\dots,\tilde{M}_{\lambda})$
by replacing $M_{i}$ by a symbol $\mathcal{E}_{k}^{\ell}$ for all
$i\in\mathcal{I}_{N}(\mathcal{R})$: the subscript is the corresponding $k\geq
2$, while $\ell$ denotes the longest $(\ell,k)$-suffix that $M_{i}=C_{k}$ can
be expanded into. Call $\mathcal{M}(\mathcal{R})$ the base sequence of
$\mathcal{R}\in\mathcal{R}_{N}$, and let
$\mathcal{A}_{N}(\mathcal{R})\in\mathcal{F}_{N}$ denote the collection of all
Zeckendorf games resulting from replacing each instance of
$\mathcal{E}_{k}^{\ell}$ in $\mathcal{M}$ by an $(l,k)$-suffix for some
$l\leq\ell$. We establish the following analogue of Lemma 4.1.

######  Proposition 4.9.

The sets $\\{\mathcal{A}_{N}(\mathcal{R})\mathrel{\mathop{\mathchar
58\relax}}\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{S}}\\}$ partition
$\Omega_{N}$.

We do not provide the proof of Proposition 4.9, as it is pursued analogously
to the proof of Proposition 4.8. The easy observation that each set
$\mathcal{A}_{N}(\mathcal{R})$, for
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$ or
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{S}}$, is a union of equivalence
classes of the corresponding sets studied in the proof of Theorem 1.11, yields
the following trivial extension of Lemma 4.5, where we promote the notation
$\mathcal{A}_{N}(\mathcal{G})=\mathcal{A}_{N}(\mathcal{R})$ for the unique
$\mathcal{R}$ satisfying $\mathcal{G}\in\mathcal{A}_{N}(\mathcal{R})$.

######  Proposition 4.10.

Say $F_{n}\leq N<F_{n+1}$. For any $c\in(0,\varphi)$ (with $\varphi$ the
golden ratio),

$\displaystyle\lim_{N\to\infty}\mu_{N}\left(\log_{2}\left|\mathcal{A}_{N}(\mathcal{G})\right|\geq
c^{n}\right)=1,$
$\displaystyle\lim_{N\to\infty}\mathbb{P}_{N}\left(\log_{2}\left|\mathcal{A}_{N}(\mathcal{G})\right|\geq
c^{n}\right)=1,$

which holds for either of the understandings
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$ and
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{S}}$.

Finally, we have the following extension of Corollary 4.3. We also omit the
proof of this result, as it is a straightforward generalization of the proof
of the aforementioned result.

######  Proposition 4.11.

Say $F_{n}\leq N<F_{n+1}$, fix some
$\mathcal{R}\in\mathcal{R}_{N}^{\mathcal{P}}$, and define random variables
$X_{1}^{\mathcal{R}},X_{2}^{\mathcal{R}},\dots,X_{N-1}^{\mathcal{R}}$
corresponding to the length of the expansion corresponding to each combine
move for a game in $\mathcal{A}_{N}(\mathcal{R})$. Under the measures
$\mu_{N}$ and $\mathbb{P}_{N}$ conditioned on $\mathcal{A}_{N}(\mathcal{R})$,
the random variables $X_{i}^{\mathcal{R}}$ are independent.

##  5\. Weak Convergence of Random Game Lengths as $N\to\infty$

In pursuit of the resolution of Conjecture 1.7, it may be productive to ask
whether there exist natural subsets of $\Omega_{N}$ on which the distribution
of random game lengths converge weakly to a Gaussian in the limit $N\to\infty$
of infinite input. As discussed in Section 4.4, the partitions defined in
Propositions 4.8 and 4.9 enjoy this property in the sense described in Theorem
1.12, restated below.

See 1.12

To explicitly define the distributions referenced in Theorem 1.12, define a
probability distribution
$\mathbb{P}_{N}^{\mathcal{R}}\mathrel{\mathop{\mathchar
58\relax}}2^{\mathcal{A}_{N}(\mathcal{R})}\to[0,1]$ via, for any
$\mathcal{S}\in 2^{\mathcal{A}_{N}(\mathcal{R})}$,

$\displaystyle\mathbb{P}_{N}^{\mathcal{R}}(\mathcal{S})=\frac{\mathbb{P}_{N}\left(\mathcal{S}\cap\mathcal{A}_{N}(\mathcal{R})\right)}{\mathbb{P}_{N}\left(\mathcal{A}_{N}(\mathcal{R})\right)}.$

Define the random variable $L_{N}^{\mathcal{R}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}_{N}(\mathcal{R})\to\mathbb{R}$ on the space
$\left(\mathcal{A}_{N}(\mathcal{R}),2^{\mathcal{A}_{N}(\mathcal{R})},\mathbb{P}_{N}^{\mathcal{R}}\right)$
by

$\displaystyle
L_{N}^{\mathcal{R}}\left((M_{1},\dots,M_{\lambda})\right)=\lambda$

for any game $(M_{1},\dots,M_{\lambda})\in\mathcal{A}_{N}(\mathcal{R})$, i.e.,
$L_{N}^{\mathcal{R}}$ studies game lengths in $\mathcal{A}_{N}(\mathcal{R})$.
Then

(3) $\displaystyle
F_{\mathcal{R}}(x)=\mathbb{P}_{N}^{\mathcal{R}}\left(\frac{L_{N}^{\mathcal{R}}-\mathbb{E}\left[L_{N}^{\mathcal{R}}\right]}{\sqrt{\text{var}\left(L_{N}^{\mathcal{R}}\right)}}\leq
x\right).$

In other words, when we restrict $\mathbb{P}_{N}$ to the sets
$\mathcal{A}_{N}(\mathcal{R})$ in the natural sense, Theorem 1.12 states that
the distribution of random game lengths enjoys weak convergence to a Gaussian
with high probability. We write

(4)
$\displaystyle\mathcal{L}_{N}^{\mathcal{R}}=\frac{L_{N}^{\mathcal{R}}-\mathbb{E}\left[L_{N}^{\mathcal{R}}\right]}{\sqrt{\text{var}\left(L_{N}^{\mathcal{R}}\right)}}$

to be the random variable $L_{N}^{\mathcal{R}}$ normalized to have mean $0$
and variance $1$. Throughout this section, we proceed on the measure
$\mathbb{P}_{N}$ and the set $\mathcal{R}_{N}^{\mathcal{P}}$, but the analysis
carries over to the uniform measure $\mu_{N}$ and the suffix partition
$\mathcal{R}_{N}^{\mathcal{S}}$.

###### Proof of Theorem 1.12.

By Proposition 4.10,
$\lim_{N\to\infty}\mathbb{P}_{N}\left(\log_{2}\left|\mathcal{A}_{N}(\mathcal{G})\right|\geq
1.6^{n}\right)=1$, so fix $\mathcal{R}\in\mathcal{R}_{N}$ such that
$|\mathcal{A}_{N}(\mathcal{R})|>2^{1.6^{n}}$, and consider the random variable
$\mathcal{L}_{N}^{\mathcal{R}}\mathrel{\mathop{\mathchar
58\relax}}\mathcal{A}_{N}(\mathcal{R})\to\mathbb{R}$. Define random
variables121212Define these to be strictly positive: if the
$i\textsuperscript{th}$ delimiter is replaced with a combine move, say
$X_{i}^{\mathcal{R}}=1$. $X_{1}^{\mathcal{R}},\dots,X_{N-1}^{\mathcal{R}}$ to
correspond to each of the combine moves in $\mathcal{R}$, with
$X_{i}^{\mathcal{R}}$ denoting the length of the corresponding prefix for a
game in $\mathcal{A}_{N}(\mathcal{R})$: by Proposition 4.11, the random
variables $X_{i}^{\mathcal{R}}$ are independent. Expanding Equation (4),

(5)
$\displaystyle\mathcal{L}_{N}^{\mathcal{R}}=\frac{L_{N}^{\mathcal{R}}-\mathbb{E}\left[L_{N}^{\mathcal{R}}\right]}{\sqrt{\text{var}\left(L_{N}^{\mathcal{R}}\right)}}=\frac{\sum_{i=1}^{N-1}\left(X_{i}^{\mathcal{R}}-\mathbb{E}\left[X_{i}^{\mathcal{R}}\right]\right)}{\sqrt{\text{var}\left(L_{N}^{\mathcal{R}}\right)}}$

where the independence (conditioned on $\mathcal{A}_{N}(\mathcal{R})$) of the
random variables $X_{i}^{\mathcal{R}}$ yields that

$\displaystyle\text{var}\left(L_{N}^{\mathcal{R}}\right)=\sum_{i=1}^{N-1}\text{var}\left(X_{i}^{\mathcal{R}}-\mathbb{E}\left[X_{i}^{\mathcal{R}}\right]\right)$

and furthermore, taking the maximum over those summands $X_{i}^{\mathcal{R}}$
which are non-constant131313Indeed, we understand
$\mathcal{L}_{N}^{\mathcal{R}}$ as the sum over the nonconstant random
variables amongst those included by the sum in Equation (5),

(6) $\displaystyle\max_{1\leq i\leq
D}\left(\frac{\mathbb{E}\left[\left|X_{i}^{\mathcal{R}}-\mathbb{E}\left[X_{i}^{\mathcal{R}}\right]\right|^{3}\right]}{\mathbb{E}\left[\left(X_{i}^{\mathcal{R}}-\mathbb{E}\left[X_{i}^{\mathcal{R}}\right]\right)^{2}\right]\cdot\text{var}\left(L_{N}^{\mathcal{R}}\right)}\right)\leq\max_{1\leq
i\leq
D}\frac{2n^{3}}{\text{var}\left(L_{N}^{\mathcal{R}}\right)}\leq\frac{n^{3}}{\text{var}\left(2^{1.6^{n}}\right)}$

and the final expression in Equation (6) certainly vanishes as $N\to\infty$.
Thus, the desired result follows immediately from the case of the Berry-Esseen
theorem for independent non-identically distributed summands, which namely
yields

$\displaystyle\sup_{x\in\mathbb{R}}\left|F_{\mathcal{R}}(x)-\Phi(x)\right|\leq
C\cdot\frac{n^{3}}{\text{var}\left(2^{1.6^{n}}\right)}\xrightarrow{N\to\infty}0$

for some universal constant $C>0$. ∎

Theorem 1.12 yields that, when restricted to particular natural subsets of
games, we have Gaussianity. The scope of this result is admittedly restricted,
especially given the result of Corollary 4.6.

##  6\. Open Problems

We conclude the work with several potential directions for further inquiry.

###  6.1. Other Two-Player Games Based on Recurrences

Theorem 1.11 can be interpreted as saying that if two players proceed
mindlessly, the Zeckendorf game is fair in the limit of infinite input;
Theorem 1.10 gives that the analogous statement would be true if we were to
extend to a $Z$-player Zeckendorf game. Many papers (such as [1, 2, 4]) have
extended the paradigm of the two-player Zeckendorf game to other recurrences:
we might ask which of these also enjoy this property. In particular, we pose
the following conjecture, concerning the two-player Bergman game ([1]).

######  Conjecture 6.1.

In the limit $N\to\infty$ of infinite input, the probabilities of Player 1 and
Player 2 winning, under both analogous definitions of random Bergman games, is
$1/2$.

The core challenges of proving Conjecture 6.1 are as follows. The principal
difference between the two-player Bergman game and the two-player Zeckendorf
game is that the move $C_{1}$ is now a split move which consumes no tokens.
Thus, there are structural differences between the two games which affects the
range of achievable game lengths. Lemma 4.5 also depends on the number of a
specific move sequence which may not have an analogue in the Bergman game.

###  6.2. Towards Gaussianity: Other Approaches

Theorem 1.12 establishes that certain natural partitions of $\Omega_{N}$ are
such that the components become arbitrarily close to being Gaussian (in the
sense of vanishing Kolmogorov-Smirnov distance) with arbitrarily high
probability: it is unclear how to extend this to the entirety of $\Omega_{N}$.
Proposition 2.6 remarks that all games in $\Omega_{N}$ can be achieved by
permutations of suffixes from a shortest game, which suggests the following
question.

######  Question 6.2.

Can we extend the techniques in Section 5 to a partition founded on the greedy
embedding of Proposition 2.6? In particular, could studying the moments of the
corresponding components lead to a proof of Conjecture 1.7?

Another possible direction is to restrict our attention to certain subsets of
moves across all of $\Omega_{N}$, rather than certain subsets of $\Omega_{N}$.
In particular, a sufficiently strong affirmative answer to Question 6.3 would
resolve Conjecture 1.7.

######  Question 6.3.

Is the distribution of the number of occurrences of a particular combine or
split move asymptotically Gaussian, under either the measure $\mu_{N}$ or
$\mathbb{P}_{N}$?

###  6.3. Towards Gaussianity: Mixing

We outline one more possible approach towards proving Conjecture 1.7, which
relies on the literature surrounding mixing central limit theorems: these are
analogues of the central limit theorem concerning sums of dependent random
variables, applicable if the dependencies amongst the summands are
sufficiently well-behaved. In particular, the main result of [6] states the
following.

######  Theorem 6.4 ([6]).

Let $\\{X_{N,i}\mathrel{\mathop{\mathchar 58\relax}}1\leq i\leq d_{N}\\}$ be a
triangular array of random variables defined on the probability space
$(\Omega,\mathcal{F},\mathbb{P})$,
$\bar{X}_{N,d_{N}}=\frac{1}{d_{N}}\sum_{i=1}^{d_{N}}X_{N,i}$, and
$\alpha_{N}\mathrel{\mathop{\mathchar 58\relax}}\mathbb{N}\to\mathbb{R}$ by

(7)
$\displaystyle\alpha_{N}(k)=\sup_{m}\sup_{A\in\mathcal{F}_{0}^{m}(N),B\in\mathcal{F}_{m+k}^{\infty}(N)}\left|\mathbb{P}(A\cap
B)-\mathbb{P}(A)\mathbb{P}(B)\right|$

where
$\mathcal{F}_{m_{1}}^{m_{2}}(N)=\sigma\left(X_{N,m_{1}},X_{N,m_{1}+1},\dots,X_{N,m_{2}}\right)$
denotes the $\sigma$-algebra generated by random variables
$X_{N,m_{1}},X_{N,m_{1}+1},\dots,X_{N,m_{2}}$. If there exists constants
$C_{1},C_{2}>0$, $\delta>0$ such that

(8)
$\displaystyle\mathbb{E}\left[\left|X_{N,i}-\mathbb{E}[X_{N,i}]\right|^{2+\delta}\right]<C_{1}$

and

(9)
$\displaystyle\sum_{k=0}^{\infty}(k+1)^{2}\alpha_{N}^{\frac{\delta}{4+\delta}}(k)<C_{2},$

then

(10)
$\displaystyle\sqrt{d_{N}}\left(\bar{X}_{N,d_{N}}-\mathbb{E}\bar{X}_{N,d_{N}}\right)\xrightarrow[N\to\infty]{\mathcal{D}}N\left(0,\text{var}\left(\sqrt{d_{N}}\bar{X}_{N,d_{N}}\right)\right).$

We can define a triangular array of Bernoulli random variables by letting
$X_{N,i}=1$ if and only if the $i$th move of a Zeckendorf game with input $N$
is a splitting move (in particular, $X_{N,i}$ maps to $0$ on the event that
the Zeckendorf game on input $N$ terminates prior to move $i$), with $d_{N}$
(the number of random variables in the $N$th row) the length of the longest
game on input $N$; Conjecture 1.7 is thus equivalent to establishing that the
row sums $\sum_{i=1}^{d_{N}}X_{N,i}$ weakly converge to a Gaussian, since the
number of combine moves for a given input $N$ is constant. This is precisely
the statement of Equation 10. Also, the events $A$ and $B$ in Equation 7 can
be understood as fixed $\\{0,1\\}$-realizations of subsets of random variables
in $\\{X_{N,1},\dots,X_{N,m}\\}$ and $\\{X_{N,m+k},\dots,X_{N,d_{N}}\\}$,
respectively.

Since Equation 8 certainly holds under this setup (the constituent random
variables are Bernoulli), resolving Conjecture 1.7 can be reduced to the
following statement.

######  Question 6.5.

For the triangular array $\\{X_{N,i}\mathrel{\mathop{\mathchar 58\relax}}1\leq
i\leq d_{N}\\}$ defined above, does there exist a constant $\delta>0$ and a
constant $C>0$ such that

(11)
$\displaystyle\sum_{k=0}^{\infty}(k+1)^{2}\alpha_{N}^{\frac{\delta}{4+\delta}}(k)<C$

for all natural numbers $N\in\mathbb{N}$?

By the preceding discussion, answering Question 6.5 in the affirmative by
establishing 11 immediately yields Conjecture 1.7. In particular, it would
suffice to establish the statement of Question 6.6 in the affirmative,
although it is not immediately clear if this should be true.

######  Question 6.6.

Does there exist a constant $\epsilon>0$ and a constant $C>0$ such that

(12) $\displaystyle\left|\mathbb{P}_{N}(A\cap
B)-\mathbb{P}_{N}(A)\mathbb{P}_{N}(B)\right|\leq\frac{C}{k^{2+\epsilon}}$

whenever events $A$ and $B$ correspond to fixed $\\{0,1\\}$-realizations of
subsets of the Bernoulli random variables in $\\{X_{N,1},\dots,X_{N,m}\\}$ and
$\\{X_{N,m+k},\dots,X_{N,d_{N}}\\}$, respectively?

Of course, the techniques introduced in the main body of this paper are quite
elementary, and there may be other promising approaches not included in this
section that would contribute towards resolving Conjecture 1.7.

## Acknowledgements

This research was conducted as part of the 2022 SMALL REU program at Williams
College, and was funded by NSF Grant DMS1947438, Harvey Mudd College, and
Williams College funds. We thank Professor Steven J. Miller and our colleagues
from the 2022 SMALL REU program, and in particular those pursuing the Zeck
Shifts project, for many helpful insights.

## References

## References

  * [1] Benjamin Baily et al.  “The Generalized Bergman Game”  arXiv, 2021  DOI: 10.48550/arXiv.2109.00117
  * [2] Paul Baird-Smith, Alyssa Epstein, Kristen Flint and Steven J. Miller  “The generalized Zeckendorf game”  In _Fibonacci Quart._ 57.5, 2019, pp. 1–14  arXiv: https://web.williams.edu/Mathematics/sjmiller/public_html/math/papers/ZeckGameGeneral_FibQ10.pdf
  * [3] Paul Baird-Smith, Alyssa Epstein, Kristen Flint and Steven J Miller  “The Zeckendorf Game”  In _Combinatorial and Additive Number Theory, New York Number Theory Seminar_ , 2018, pp. 25–38  Springer
  * [4] Elżbieta Bołdyriew et al.  “Extending Zeckendorf’s Theorem to a Non-constant Recurrence and the Zeckendorf Game on this Non-constant Recurrence Relation”  In _arXiv preprint arXiv:2009.12475_ , 2020
  * [5] Anna Cusenza et al.  “Bounds on Zeckendorf games”  In _Fibonacci Quart._ 60.1, 2022, pp. 57–71
  * [6] Magnus Ekström  “A general central limit theorem for strong mixing sequences”  In _Statistics & Probability Letters_ 94 Elsevier, 2014, pp. 236–238
  * [7] Ruoci Li et al.  “Deterministic Zeckendorf Games”  In _arXiv preprint arXiv:2006.16457_ , 2020
  * [8] Steven J. Miller  “Private communication”, 2022
  * [9] Edouard Zeckendorf  “Representations des nombres naturels par une somme de nombres de fibonacci on de nombres de lucas”  In _Bulletin de La Society Royale des Sciences de Liege_ , 1972, pp. 179–182