WYTHOFF’S SEQUENCE AND N-HEAP WYTHOFF’S CONJECTURES

XINYU SUN

Abstract. Define a Wythoff’s sequence as a sequence of pairs of integers {(A_{n}, B_{n})}_{n>n_{0}} so that there exists a finite set of integers T, A_{n} = mex({A_{i}, B_{i} : i < n} ∪ T), B_{n} − A_{n} = n, and {B_{n}} ∩ T = ∅. Structural properties and behaviors of Wythoff’s sequence are investigated. The main result is that for such a sequence, there always exists an integer α so that when n is large enough, |A_{n} − ⌊nϕ⌋ − α| ≤ 1, where ϕ = (1 + \sqrt{5})/2, the golden section. The value of α can also be easily determined by a relatively small number of pairs in the sequence. As a corollary, the two conjectures on the N-heap Wythoff’s game by Fraenkel [2] are proved to be equivalent.

1. Introduction

Wythoff’s pairs are pairs of integers \{(⌊nϕ⌋, ⌊nϕ^{2}⌋)\}_{n≥0}, where ϕ = (1+\sqrt{5})/2, the golden section, which notation we adopt throughout this paper. The first few pairs are listed in the following table:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 \\ A_{n} = ⌊nϕ⌋ & 0 & 1 & 3 & 4 & 6 & 8 & 9 & 11 & 12 & 14 & 16 & 17 & 19 & 21 \\ B_{n} = ⌊nϕ^{2}⌋ & 0 & 2 & 5 & 7 & 10 & 13 & 15 & 18 & 20 & 23 & 26 & 28 & 31 & 34 \end{matrix}

Wythoff’s pairs have close relationships with the Fibonacci numbers. For example, let us consider the sequence A_{1}, B_{1}, A_{B_{1}}, B_{B_{1}}, A_{B_{B_{1}}}, B_{B_{B_{1}}}, …, which is 1, 2, 3, 5, 8, 13, 21, 34, …, which in turn is the Fibonacci sequence without the first number. In fact, any such sequence starting from A_{n} and B_{n} is a Fibonacci sequence generated by those two integers, as proved by Hoggatt and Hillman [6], Horadam [7], and Silber [8]. Other properties, relationships and applications were investigated extensively by numerous people, whom we are not going to list here.

Wythoff’s pairs were first found as the result of a mathematical game [10]: the game consisting of two piles of tokens, and two players take turns to remove any number of tokens from a single pile, or the same number of tokens from both piles. The first player who cannot make a move loses. Wythoff’s pairs can therefore be interpreted as {A_{n}, B_{n}}_{n≥0}, so that A_{n} = mex{A_{m}, B_{m} : 0 ≤ m < n} and B_{n} = A_{n} + n with A_{0} = B_{0} = 0, where mex is the Minimal EXclusive value, i.e., the least nonnegative integer that is not in the set. The winning strategies were described by Fraenkel [3], and also in WW [1]. and periodic properties of the Sprague-Grundy function and other generalizations of the game were also discussed. Please see the manuscript by Fraenkel [2] for a complete list of the progress.

Another elegant generalization of the game involving more than two piles was proposed by Fraenkel [2], which is also listed by Guy and Nowakowski [4] as one of the “unsolved problems in combinatorial games”: given N piles of tokens, whose sizes are A^{1}, …, A^{N}, A^{1} ≤ ⋯ ≤ A^{N}. A player can remove any number of tokens from a single pile, or remove (a_{1}, …, a_{N}) tokens from all piles — a_{i} tokens from the i-th pile, providing that 0 ≤ a_{i} ≤ A^{i}, ∑_{i=1}^{N} a_{i} > 0, and a_{1} ⊕ ⋯ ⊕ a_{N} = 0, where ⊕ is the nim addition (XOR binary operation). Denote all the P -positions by (A^{1}, …, A^{N−2}, A_{n}^{N−1}, A_{n}^{N}), A^{N−2} ≤ A_{n}^{N−1} ≤ A_{n}^{N} and A_{n}^{N−1} < A_{n+1}^{N−1} for all n ≥ 0. Two conjectures were presented on the game, when A^{1}, …, A^{N−2} are fixed:

Conjecture 1: There exists an integer N_{1} so that when n > N_{1}, A_{n}^{N} = A_{n}^{N−1} + n.

Conjecture 2: There exist integers N_{2} and α_{2} so that when n > N_{2}, A_{n}^{N−1} = ⌊nϕ⌋+ϵ_{n} +α_{2} and A_{n}^{N} = A_{n}^{N−1} + n, where −1 ≤ ϵ_{n} ≤ 1.

Furthermore, A_{n}^{N−1} = mex({A_{i}^{N−1}, A_{i}^{N} : 0 ≤ i < n} ∪ T), where T is a small set of integers.

By preserving the moves related to the nim addition, the winning strategy of the multipleheap Wythoff’s game seems to have retained the golden section, just as the original game did. Doron Zeilberger and the author [9] proved the conjectures for the three-heap game when the first heap has up to 10 tokens.

In this paper, we are going to discuss the definition of Wythoff’s sequence and its construction in section 2, the basic properties of Wythoff’s sequence in section 3, and special Wythoff’s sequence and the equivalency of the two conjectures on N-heap Wythoff’s game in section 4.

2. Wythoff’s Sequence

Definition 1. We call a sequence of pairs of integers {(A_{n}, B_{n})}_{n≥n_{0}} a Wythoff’s sequence if there exist a finite set of integers T so that A_{n} = mex({A_{i}, B_{i} : n_{0} ≤ i < n}∪T), B_{n} = A_{n}+n and {B_{n}} ∩ T = ∅. Definition 2. A special Wythoff’s sequence is a Wythoff’s sequence such that there exist integers N and α so that when n > N, A_{n} = ⌊nϕ⌋ + α + ϵ_{n}, where ϵ_{n} ∈ {0, ±1}.

When it is not confusing, we will abuse the definition of (special) Wythoff’s sequence by replacing the requirement of B_{n} = A_{n} + n to B_{n+1} − A_{n+1} = B_{n} − A_{n} + 1 when n is large enough, because we can easily obtain a Wythoff’s sequence by chopping off a number of pairs at the beginning of the sequence and reorganizing the remaining indices.

The following theorem provides another way to create a Wythoff’s sequence.

Theorem 2.1. {(A_{n}, B_{n})} is a Wythoff’s sequence if and only if there exist two finite sets of integers S_{1} and S_{2} ⊂ ℤ_{≥0}, so that A_{n} = mex({A_{i}, B_{i} : i < n}∪S_{1}), B_{n} = mex{{A_{n}+B_{i}−A_{i} : i < n} ∪ {A_{n} + t : t ∈ S_{2}} ∪ S_{1}}. In such a case, S_{2} = ℤ_{≥0} − {B_{i} − A_{i} : i > 0}.

Proof: Given S_{1} and S_{2} are as described above, there exists N_{0} so that when n ≥ N_{0}, A_{n} > max(S_{1}) and B_{n} − A_{n} > max(S_{2}). Denote α_{n} = max{B_{i} − A_{i} : i < n} + 1 and D_{n} = {i : 0 ≤ i < α_{n}} − S_{2} − {B_{i} − A_{i} : i < n}. Then for any n ≥ N_{0}, it is obvious that B_{n}−A_{n} ≤ α_{n}. Now B_{n}−A_{n} < α_{n} iff B_{n}−A_{n} ∈ D_{n}; iff α_{n+1} = α_{n}; iff D_{n} = D_{n+1}∪{B_{n}−A_{n}}. Also, B_{n} − A_{n} = α_{n} iff α_{n+1} = α_{n} + 1; iff D_{n+1} = D_{n}. Note that D_{n+1} ⊂ D_{n} ⊂ D_{n_{0}} are all finite, so there exists N ≥ N_{0} such that for any n ≥ N, D_{n} = D_{n+1}, and B_{n+1} − A_{n+1} = α_{n+1} = α_{n} + 1 = B_{n} − A_{n} + 1.

Now supposedly there exists d ∈ ℤ_{≥0} −{B_{i} −A_{i} : i > 0}−S_{2}, then for any n large enough, there exists m < n so that A_{n}+d = B_{m}. Therefore for any n large enough, there exist m_{1} and m_{2} so that A_{n+1} − A_{n} = B_{m_{1}} − B_{m_{2}}. By Lemma 3.1 in the following section, A_{n+1} − A_{n} = 2 and B_{n+1} − B_{n} = A_{n+1} − A_{n} + 1 = 3. Given any such n, A_{3n} = 2(3n − n) + A_{n} = 4n + A_{n} = 3n + B_{n} = 3(2n − n) + B_{n} = B_{2n}, which is contradictory to Definition 1.

Conversely, if {(A_{n}, B_{n})} is a Wythoff’s sequence, we can define S_{1} = ℤ_{≥0}−{A_{i}, B_{i} : i > 0} and S_{2} = ℤ_{≥0} − {B_{i} − A_{i} : i > 0}, which are both finite by the definition of the Wythoff’s sequence.

So even though we can start with two random finite sets of integers, S_{1} and S_{2}, so that {A_{n}, B_{n}} ∩ S_{1} = ∅ and {B_{n} − A_{n}} ∩ S_{2} = ∅, after some chaotic data at the beginning, the sequence of pairs of integers {(A_{n}, B_{n})} defined in the theorem will eventually grow in an orderly manner, and become a Wythoff’s sequence.

3. Properties of Wythoff’s Sequence

From this section and on, for any Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}}, we always assume that when n ≥ n_{0}, A_{n_{0}} > max(T) as in Definition 2.1; or equivalently, A_{n_{0}} > max(S_{1}), B_{n_{0}} > A_{n_{0}} + max(S_{2}) + 1 and B_{n+1} − A_{n+1} = B_{n} − A_{n} + 1 as in Theorem 2.1. Otherwise, we can always increase the value of n_{0}. Lemma 3.1. Given a Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}},

(1) 1 ≤ A_{n+1} − A_{n} ≤ 2,

(2) 2 ≤ B_{n+1} − B_{n} ≤ 3, and

(3) |⌊n_{1}ϕ⌋ − ⌊n_{2}ϕ⌋ − (n_{1} − n_{2})ϕ| < 1.

Proof: See [9]. Theorem 3.2. Given a Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}}, there exists a constant c, so that A_{A_{n}+c} = B_{n} − 1 and A_{B_{n}+c} = B_{A_{n}+c} + 1 = A_{n} + B_{n} + c.

Proof: By lemma 3.1, there exists k_{0} so that A_{k_{0}} = B_{n_{0}} − 1. Consider all the integers from 1 to B_{n_{0}} − 1, there are (k_{0} − n_{0} + 1) A’s, no B’s, and |T | T ’s, which means B_{n_{0}} − 1 = |T | + k_{0} − n_{0} + 1. Denote c = k_{0} − A_{n_{0}}. We can have |T | = B_{n_{0}} − 1 − k_{0} + n_{0} − 1 = A_{n_{0}} − k_{0} + 2n_{0} − 2 = 2n_{0} − 2 − c.

Now for any n ≥ n_{0}, there exists A_{k} = B_{n}−1. Consider all the integers from 1 to B_{n}, there are (k−n_{0}+1) A’s, (n−n_{0}+1) B’s, and |T | T ’s, so B_{n} = k−n_{0}+1+n−n_{0}+1+|T | = k+n−c, hence k = B_{n} − n + c = A_{n} + c. Therefore B_{n} = A_{k} + 1 = A_{A_{n}+c} + 1.

Consider all the integers from 1 to B_{A_{n}+c}, there are (A_{n} + c − n_{0} + 1) B’s and |T | T ’s, so there are (B_{A_{n}+c} − A_{n} − c + n_{0} − 1 − |T |) = (A_{A_{n}+c} + n_{0} − 1 − |T |) A’s, the largest of which is A_{k′} = B_{A_{n}+c} − 1, where k′ must be A_{A_{n}+c} + n_{0} − 1 − |T | + n_{0} − 1 = B_{n} − 1 + 2n_{0} − 2 − (2n_{0} − 2 − c) = B_{n} + c − 1. By Lemma 3.1 and the previous result, A_{B_{n}+c} = A_{k′+1} = B_{A_{n}+c} + 1 = A_{A_{n}+c} + A_{n} + c + 1 = A_{n} + B_{n} + c. Corollary 3.3. Given a Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}} and c as in Theorem 3.2, A_{A_{n}+c+1} − A_{A_{n}+c} = 2; A_{B_{n}+c+1} − A_{B_{n}+c} = 1; B_{A_{n}+c+1} − B_{A_{n}+c} = 3; B_{B_{n}+c+1} − B_{B_{n}+c} = 2.

Proof: A_{m+c+1} − A_{m+c} = 2 iff there exists n, so that A_{m+c+1} − 1 = B_{n} = A_{m+c} + 1; iff A_{m+c} = A_{A_{n}+c}; iff m = A_{n}. The rest of the equations are obvious from the preceding fact and are left to interested readers.

Notice that if there exist m_{1} > m_{2} > n_{0}, so that A_{m_{1}} ≥ B_{m_{2}} and we know {(A_{n}, B_{n}) : m_{2} ≤ n ≤ m_{1}}, we can construct the sequence for m > m_{1} without using the definition of the Wythoff’s sequence, i.e., mex. There are two ways of doing so recursively:

(1) For any m > m_{1}, by Theorem 3.2, if m−c is of the form A_{m′}, A_{m} = A_{m′} +m′ −1 and B_{m} = m+B_{m′} −1; otherwise, m−c = B_{m′}, A_{m} = A_{m′} +m and B_{m} = B_{m′} +2m−m′.

(2) If A_{m} is known and if m − c is in the A’s, by Corollary 3.3, A_{m+1} = A_{m} + 2 and B_{m+1} = B_{m} + 3; otherwise, A_{m+1} = A_{m} + 1 and B_{m+1} = B_{m} + 2. Here we can see that the two sequences are self-generating, i.e., we can construct the sequence of {A_{n}}_{n≥m_{2}} or {B_{n}}_{n≥m_{2}} without any knowledge of the other.

Corollary 3.4. Given a Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}}, then for any n ≥ A_{n_{0}}, the number of A’s less than n is A_{n+c} − n − n_{0} + 1; for any n ≥ B_{n_{0}}, the number of B’s less than n is 2n − A_{n+c} + c − n_{0}.

Proof: Denote f(n) = A_{n+c} −n−n_{0} +1. We claim that f(n) is the number of A’s less than n. First, f(A_{n_{0}}) = A_{A_{n_{0}}+c} − A_{n_{0}} − n_{0} + 1 = B_{n_{0}} − A_{n_{0}} − n_{0} = 0, which is the number of A’s less than A_{n_{0}}. By induction, if the claim is true for n − 1, there are two cases: if n − 1 = B_{m}, by Corollary 3.3, f(n) = A_{B_{m}+1+c} − (B_{m} + 1) − n_{0} + 1 = A_{B_{m}+c} − B_{m} − n_{0} + 1 = f(n − 1); if n − 1 = A_{m}, f(n) = A_{A_{m}+1+c} − (A_{m} + 1) − n_{0} + 1 = A_{A_{m}+c} + 2 − A_{m} − n_{0} = f(n − 1) + 1. So the claim is true. On the other hand, if we write g(n) = 2n − A_{n+c} + c − n_{0}, g(B_{n_{0}}) = 2B_{n_{0}} − A_{B_{n_{0}}+c} + c − n_{0} = 2B_{n_{0}} − A_{n_{0}} − B_{n_{0}} − c + c − n_{0} = 0. If n > B_{n_{0}} and if n − 1 = B_{m}, g(n) = 2n − A_{B_{m}+1+c} − n_{0} = 2n − A_{B_{m}+c} − 1 − n_{0} = g(n − 1) + 1; if n − 1 = A_{m}, g(n) = 2n − A_{A_{m}+1+c} − n_{0} = 2n − A_{A_{m}+c} − 2 − n_{0} = g(n − 1). So g(n) is the number of B’s less than n.

A special case of the theorem and corollaries is when the Wythoff’s sequence is the original Wythoff’s pairs. In such an occasion, n_{0} = 0 and c = 0, which were proved by Hoggatt, Hillman [6], Hoggatt, Bicknell-Johnson [5], and Silber [8].

4. Special Wythoff’s Sequence and N-heap Wythoff’s Conjectures

Throughout this section we use Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}} and c as in Theorem 3.2. Note that when n is large enough, it must be of the form A_{A_{m}}, A_{B_{m}}, B_{A_{m}}, or B_{B_{m}}. Since for any m, there exist m_{1} and m_{2} such that A_{m} = B_{m_{1}} ± 1 and B_{m} = A_{m_{2}} + 1, so n must be of the form B_{A_{m}+c+ϵ_{2}} + c + ϵ_{1}, where ϵ_{1} ∈ {−1, 0, 1} and ϵ_{2} ∈ {0, 1}.

Theorem 4.1. Every Wythoff’s sequence is special.

Proof: Denote α_{n} = A_{n} − ⌊nϕ⌋. We only need to prove that as m and n grow, |α_{m} − α_{n}| eventually decreases to at most 2.

By Corollary 3.3, A_{B_{n}+c+1} − A_{B_{n}+c} − ϕ = 1 − ϕ and A_{B_{n}+c−1} − A_{B_{n}+c} + ϕ = −2 + ϕ, so A_{B_{n}+c+ϵ} − A_{B_{n}+c} − ϕϵ = (3ϵ − 2ϕϵ − ϵ^{2})/2 when |ϵ| ≤ 1. Therefore if we denote γ = (A_{B_{m}+c+ϵ_{m}} − A_{B_{m}+c} − ϕϵ_{m}) − (A_{B_{n}+c+ϵ_{n}} − A_{B_{n}+c} − ϕϵ_{n}), |γ| = |(ϵ_{m} − ϵ_{n})(3 − 2ϕ − ϵ_{m} − ϵ_{n})/2| ≤ ϕ − 1, when |ϵ_{m}|, |ϵ_{n}| ≤ 1. Also note that A_{A_{n}+c+ϵ} − A_{A_{n}+c} = 2ϵ, when ϵ ∈ {0, 1}.

We also adopt the following notations: β_{1} = ⌊(B_{A_{m}+c+ϵ_{2m}} + c + ϵ_{1m})ϕ⌋ − ⌊(B_{A_{n}+c+ϵ_{2n}} + c + ϵ_{1n})ϕ⌋−((B_{A_{m}+c+ϵ_{2m}} +c+ϵ_{1m})ϕ−(B_{A_{n}+c+ϵ_{2n}} +c+ϵ_{1n})ϕ) and β_{2} = ⌊mϕ⌋−⌊nϕ⌋−(m−n)ϕ.

Now if ϵ_{1m}, ϵ_{1n} ∈ {−1, 0, 1} and ϵ_{2m}, ϵ_{2n} ∈ {0, 1},

α_{B_{Am+c+ϵ_{2m}}+c+ϵ_{1m}} − α_{B_{An+c+ϵ_{2n}}+c+ϵ_{1n}}
= A_{B_{Am+c+ϵ_{2m}}+c+ϵ_{1m}} − A_{B_{An+c+ϵ_{2n}}+c+ϵ_{1n}}
−(⌊(B_{A_{m}+c+ϵ_{2m}} + c + ϵ_{1m})ϕ⌋ − ⌊(B_{A_{n}+c+ϵ_{2n}} + c + ϵ_{1n})ϕ⌋)
= A_{B_{Am+c+ϵ_{2m}}+c+ϵ_{1m}} − A_{B_{An+c+ϵ_{2n}}+c+ϵ_{1n}}
−((B_{A_{m}+c+ϵ_{2m}} − B_{A_{n}+c+ϵ_{2n}})ϕ + (ϵ_{1m} − ϵ_{1n})ϕ + β_{1})
= A_{B_{Am+c+ϵ_{2m}}+c} − A_{B_{An+c+ϵ_{2n}}+c} + γ − (B_{A_{m}+c+ϵ_{2m}} − B_{A_{n}+c+ϵ_{2n}})ϕ − β_{1}
= A_{A_{m}+c+ϵ_{2m}} − A_{A_{n}+c+ϵ_{2n}} + (B_{A_{m}+c+ϵ_{2m}} − B_{A_{n}+c+ϵ_{2n}})(1 − ϕ) + γ − β_{1}
= (A_{A_{m}+c+ϵ_{2m}} − A_{A_{n}+c+ϵ_{2n}})(2 − ϕ) + (A_{m} − A_{n} + ϵ_{2m} − ϵ_{2n})(1 − ϕ) + γ − β_{1}
= (A_{A_{m}+c} − A_{A_{n}+c} + 2(ϵ_{2m} − ϵ_{2n}))(2 − ϕ) + (A_{m} − A_{n} + ϵ_{2m} − ϵ_{2n})(1 − ϕ) + γ − β_{1}
= (A_{A_{m}+c} − A_{A_{n}+c})(2 − ϕ) + (A_{m} − A_{n})(1 − ϕ) + (ϵ_{2m} − ϵ_{2n})(5 − 3ϕ) + γ − β_{1}

= (B_{m} − B_{n})(2 − ϕ) + (A_{m} − A_{n})(1 − ϕ) + (ϵ_{2m} − ϵ_{2n})(5 − 3ϕ) + γ − β_{1}
= (A_{m} − A_{n})(3 − 2ϕ) + (m − n)(2 − ϕ) + (ϵ_{2m} − ϵ_{2n})(5 − 3ϕ) + γ − β_{1}
= (⌊mϕ⌋ + α_{m} − ⌊nϕ⌋ − α_{n})(3 − 2ϕ) + (m − n)(2 − ϕ) + (ϵ_{2m} − ϵ_{2n})(5 − 3ϕ) + γ − β_{1}
= ((m − n)ϕ + β_{2} + (α_{m} − α_{n}))(3 − 2ϕ) + (m − n)(2 − ϕ)

+(ϵ_{2m} − ϵ_{2n})(5 − 3ϕ) + γ − β_{1}

= −(α_{m} − α_{n}))(2ϕ − 3) − β_{2}(2ϕ − 3) + (ϵ_{2m} − ϵ_{2n})(5 − 3ϕ) + γ − β_{1}.

\begin{matrix}So & |α_{B_{Am+c+ϵ_{2m}}+c+ϵ_{1m}} − α_{B_{An+c+ϵ_{2n}}+c+ϵ_{1n}}| \\ ≤ & |α_{m} − α_{n}|(2ϕ − 3) + |β_{2}|(2ϕ − 3) + |ϵ_{2m} − ϵ_{2n}|(5 − 3ϕ) + |γ| + |β_{1}| \\ < & |α_{m} − α_{n}|(2ϕ − 3) + (2ϕ − 3) + (5 − 3ϕ) + ϕ − 1 + 1 \\ = & |α_{m} − α_{n}|(2ϕ − 3) + 2. \end{matrix}

Since it is an integer, |α_{B_{Am+c+ϵ_{2m}}+c+ϵ_{1m}} − α_{B_{An+c+ϵ_{2n}}+c+ϵ_{1n}}| ≤ max(|α_{m} − α_{n}| − 1, 2). So for any integers m and n, we can construct two sequences a_{1}, …, a_{k} and b_{1}, …, b_{k}, such that a_{k} = m, b_{k} = n, a_{i} = B_{A_{a_{i−1}}+c+ϵ_{a2i}} + ϵ_{a1i} and b_{i} = B_{A_{b_{i−1}}+c+ϵ_{b2i}} + ϵ_{b1i}, where 1 < i ≤ k, ϵ_{a1i}, ϵ_{b1i} ∈ {0, ±1} and ϵ_{a2i}, ϵ_{b2i} ∈ {0, 1}. Then when k is large enough, i.e., when m and n are large enough, |α_{a_{i}} − α_{b_{i}}| decreases to at most 2.

Using the same method, we can investigate the behavior of the sequence {α_{m}}_{m≥n_{0}}:

Denote β_{3} = (⌊A_{m}ϕ⌋ − ⌊A_{n}ϕ⌋) − (A_{m} − A_{n})ϕ, and β_{4} = (⌊mϕ⌋ − ⌊nϕ⌋) − (m − n)ϕ.

α_{A_{m}} − α_{A_{n}}

= A_{A_{m}} − A_{A_{n}} − (⌊A_{m}ϕ⌋ − ⌊A_{n}ϕ⌋)
= B_{m} − B_{n} − (A_{m} − A_{n})ϕ − β_{3}
= (A_{m} − A_{n})(1 − ϕ) + (m − n) − β_{3}
= (⌊mϕ⌋ − ⌊nϕ⌋ + α_{m} − α_{n})(1 − ϕ) + (m − n) − β_{3}
= (m − n)ϕ + β_{4} + α_{m} − α_{n})(1 − ϕ) + (m − n) − β_{3}
= −(α_{m} − α_{n})(ϕ − 1) − β_{3} − β_{4}(ϕ − 1).

So when |α_{m} − α_{n}| ≥ 3, (α_{A_{m}} − α_{A_{n}}) and (α_{m} − α_{n}) always have different signs. Together with the fact that |α_{m+1} − α_{m}| = |A_{m+1} − A_{m} − (⌊(m + 1)ϕ⌋ − ⌊mϕ⌋)| ≤ 1, let us consider α(m) = α_{m} as a function. The graph of the function is a set of discrete points that oscillate. The amplitude of graph, if we are allowed to abuse the word, decreases slowly but persistently as m grows. By Theorem 4.1, the amplitude eventually decreases to 1, when the oscillation of the graph becomes somewhat unpredictable.

Lemma 4.2. In the two conjectures on the N-heap Wythoff’s game, A_{n}^{N−1} = mex({A_{i}^{N−1}, A_{i}^{N} : 0 ≤ i < n} ∪ T), where T is a finite set depending only on A^{1}, …, A^{N−2}. In fact, T = {a : ∃b ≤ A^{N−2} and k ≤ N −2, such that A^{k−1} ≤ b ≤ A^{k} and (A^{1}, …, A^{k−1}, b, A^{k}, …, A^{N−2},

a) is a P -position}.

Proof: By definition, T = ℤ_{≥0} − {A_{i}^{N−1}, A_{i}^{N} : i > 0}. Denote T′ as the last set in the lemma. We claim T = T′. First, T′ ⊂ T because for any b ≥ a, (A^{1}, …, A^{N−2}, a, b) is an N-position since we can remove tokens from the last pile to create a P -position; and similar argument can be applied when A^{N−2} < b < a.

For any a ∈ T and b ≥ a, (A^{1}, …, A^{N−2}, a, b) is an N-position by the definition of T. There are several kind of moves from this position to create a P -position:

(1) Remove a_{1}, …, a_{N} tokens from all corresponding piles, where a_{1} ⊕ ⋯ ⊕ a_{N} = 0, so that (A^{1} − a_{1}, …, A^{N−2} − a_{N−2}, a − a_{N−1}, b − a_{N}) is a P -position.

(2) Remove a_{k} ≤ A^{k} tokens from the k-th pile, so that (A^{1}, …, A^{k−1}, A^{k} − a_{k}, A^{k+1}, …, A^{N−2}, a, b) is a P -position;

(3) Remove a_{N−1} ≤ a tokens from the (N −1)-th pile, so that (A^{1}, …, A^{N−2}, a−a_{N−1}, b) is a P -position;

(4) Remove a_{N} ≤ b tokens from the N-th pile, so that (A^{1}, …, A^{N−2}, a, b − a_{N}) is a P -position;

There are only finitely many possible moves using the first three kinds of moves, but there are infinitely many choices of b, so there exists an integer b′ such that (A^{1}, …, A^{N−2}, a, b−b′) is a P -position. Again by the definition of T and by the convention that we adopted: A^{1} ≤ ⋯ ≤ A^{N−2} ≤ a ≤ b, we must have b − b′ ≤ A^{N−2}, which shows T ⊂ T′. T′ is obviously finite, since A^{1} ≤ ⋯ ≤ A^{N−2} are finite.

Now denote a = mex({A_{i}^{N−1}, A_{i}^{N} : 0 ≤ i < n} ∪ T). It is obvious that A_{n}^{N−1} ≥ a. Also, by the definition of T and mex, (A^{1}, …, A^{N−2}, c, a) is an N-positionfor any A^{N−2} ≤ c < a, but there must exist an integer b ≥ a such that (A^{1}, …, A^{N−2}, a, b) is a P -position. Finally, since we assume A_{n−1}^{N−1} < A_{n}^{N−1}, if there exists b such that A_{n−1}^{N−1} < b < A_{n}^{N−1}, we must have either b ∈ T or b ∈ {A_{i}^{N}}_{i≥1}. Combining all the arguments above, a = A_{n}^{N−1}. Corollary 4.3. The two conjectures on the N-heap Wythoff’s game are equivalent.

Proof: Conjecture 1, together with the previous lemma, states that the P -positions for any given m form a Wythoff’s sequence, while Conjecture 2 states further that it is a special Wythoff’s sequence. The result follows from Theorem 4.1. Theorem 4.4. Given a Wythoff’s sequence {(A_{n}, B_{n})}_{n≥n_{0}} and α are as in Definition 2, α = −c.

Proof: Denote β_{5} = ⌊(A_{n} + c)ϕ⌋ − (A_{n} + c)ϕ and β_{6} = ⌊nϕ⌋ − nϕ. Then A_{n} + n − 1 = B_{n}−1 = A_{A_{n}+c} = ⌊(A_{n}+c)ϕ⌋+α+ϵ_{A_{n}+c} = A_{n}ϕ+cϕ+α+ϵ_{A_{n}+c}+β_{5}. So ϵ_{A_{n}+c}+β_{5} = A_{n}(1− ϕ)−1+n−cϕ−α = (nϕ+α+ϵ_{n}+β_{6})(1−ϕ)+n−cϕ−α−1 = −(c+α)ϕ+(ϵ_{n}+β_{6})(1−ϕ)−1, hence −(c + α)ϕ = ϵ_{A_{n}+c} + β_{5} + (ϵ_{n} + β_{6})(ϕ − 1) + 1.

Note that the left-hand side of the last equation does not depend on the choice of n, while the right-hand side does. The theorem is proved if we can make the right choice of n so that the absolute value of the right-hand side is less than ϕ. Note that −1 < β_{5}, β_{6} < 0, and ϵ_{A_{n}+c}, ϵ_{n} ∈ {0, ±1}, therefore the proof is completed if we can find an integer N so that

(4.1)  ϵ_{A_{N} +c} = 0; or
(4.2)  ϵ_{N} = 0 and ϵ_{A_{N} +c} ∈ {0, −1}; or

ϵ_{N} = −1 and ϵ_{A_{N} +c} ∈ {0, 1}. (4.3)

First we can assume ϵ_{n} is not a constant, otherwise we can adjust the value of α so that ϵ_{n} is always 0. Secondly, since |ϵ_{n}| ≤ 1 and |ϵ_{n}−ϵ_{n−1}| ≤ |(A_{n}−A_{n−1})−(⌊nϕ⌋−⌊(n−1)ϕ⌋)| ≤ 1, there always exists an n large enough so that ϵ_{n} = 0. By the condition 4.2 above, we only have to consider the case for when ϵ_{n} = 0 and ϵ_{A_{n}+c} = 1. From now on, we always assume n is large enough.

If A_{n} = A_{n−1}+1, by Corollary 3.3, there exist m so that n = B_{m}+1+c; and by Lemma 3.1, there exists m′ so that B_{m} + 1 = A_{m′}. Therefore, ϵ_{A_{m′}+c} = ϵ_{n} = 0, which proves the theorem by choosing N = m′ and using condition 4.1.

If A_{n} = A_{n−1} + 2, 3 ≤ ⌊(A_{n} + c)ϕ⌋ − ⌊(A_{n−1} + c)ϕ⌋ ≤ 4. There also exists m so that A_{n−1} + 1 = B_{m} = A_{A_{m}+c} + 1, therefore n − 1 = A_{m} + c. Furthermore A_{A_{n}+c} − A_{A_{n−1}+c} = (A_{B_{m}+1+c} − A_{B_{m}+c}) + (A_{B_{m}+c} − A_{B_{m}−1+c}) = 3 by Corollary 3.3, which means ⌊(A_{n} + c)ϕ⌋ − ⌊(A_{n−1}+c)ϕ⌋+ϵ_{A_{n}+c}−ϵ_{A_{n−1}+c} = 3. Therefore ⌊(A_{n}+c)ϕ⌋−⌊(A_{n−1}+c)ϕ⌋ = 3 and ϵ_{A_{n−1}+c} = 1, because of our assumption of ϵ_{A_{n}+c} = 1. Since 2 = A_{n} −A_{n−1} = ⌊nϕ⌋−⌊(n−1)ϕ⌋−ϵ_{n−1}, we have either ⌊nϕ⌋ − ⌊(n − 1)ϕ⌋ = 1 and ϵ_{n−1} = −1, or ⌊nϕ⌋ − ⌊(n − 1)ϕ⌋ = 2 and ϵ_{n−1} = 0. In the former case we have proved the theorem by choosing N = n − 1 and using condition 4.3 because ϵ_{n−1} = −1 and ϵ_{A_{n−1}+c} = 1; while in the latter case ϵ_{A_{m}+c} = ϵ_{n−1} = 0, so we can choose N = m and use condition 4.1.

The theorem indicates that the value of α is in fact −c, which is determined by the values of the pairs (A_{i}, B_{i}) at the beginning of the sequence. As shown in the proof of Theorem 3.2, all we need to know is the integer k so that A_{k} = B_{n_{0}} − 1, which is to find all the A’s less than B_{n_{0}}. So by using the notations in the proof of Corollary 3.4, f(B_{n_{0}}) = A_{B_{n_{0}}+c} − B_{n_{0}} − n_{0} + 1 = A_{n_{0}} − n_{0} + 1 + c = B_{n_{0}} − 2n_{0} + 1 + c, therefore it only requires the calculation of the values of roughly B_{n_{0}} − 2n_{0} + 1 pairs of integers.

5. Remarks and Acknowledgements

Many thanks to my advisor Doron Zeilberger for his encouragement and support throughout the development of this paper.

Lemma 3.1 and Corollary 4.3, and maybe some others, were also independently discovered by Aviezri Fraenkel and Dalia Krieger. This paper benefited tremendously from their comments and suggestions on the draft copy, which have made it much clearer and much more readable.

References

1. E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways for your Mathematical Plays, Vol. I & II, Academic Press, London, 1982. 2nd edition, A. K. Peters, Natick, MA, 2001

2. A. S. Fraenkel, Complexity, appeal and challenges of combinatorial Games, to appear in Theoret. Comp. Sci., special issue on Algorithmic Combinatorial Game Theory.

3. A. S. Fraenkel, How to beat your Wythoff games’ opponent on three fronts, Amer. Math. Monthly 89 (1982) 353–361.

4. R. K. Guy and R. J. Nowakowski, Unsolved problems in combinatorial games, in: More Games of No Chance, Cambridge University Press, Cambridge, 2002, 457–473.

5. V. E. Hoggatt, Jr. and M. Bicknell-Johnson, Sequence transforms related to representations using generalized Fibonacci numbers. Fibonacci Quart. 20 (1982) 289–298.

6. V. E. Hoggatt, Jr.; A. P. Hillman, A property of Wythoff pairs. Fibonacci Quart. 16 (1978) 472.

7. A. F. Horadam, Wythoff pairs. Fibonacci Quart. 16 (1978) 147–151.

8. R. Silber, A Fibonacci property of Wythoff pairs. Fibonacci Quart. 14 (1976) 380–384.

9. X. Sun and D. Zeilberger, On Fraenkel’s N-heap Wythoff’s conjecture, preprint.

10. W. A. Wythoff, A modification of the game of Nim, Nieuw Arch. Wisk. 7 (1907) 199–202.

Department of Mathematics, Temple University, Philadelphia, PA 19122

  E-mail address: xysun@math.temple.edu