\documentclass[12pt]{amsart}
\usepackage{amsfonts,amsmath,amstext,amsbsy,euscript,amssymb, graphics}
\setlength{\oddsidemargin}{0.0in}
\setlength{\evensidemargin}{0.0in}
\setlength{\textwidth}{6.5in}
\setlength{\parskip}{1.5ex}


%\documentstyle{amsart}

%\newcommand{\AmS}{\leavevmode\hbox{$\cal A\kern-.1667em
%  \lower.5ex\hbox{$\cal M$}\kern-.125em\cal S$}}

\makeatletter
 \def\LaTeX{\leavevmode L\raise.42ex
   \hbox{\kern-.3em\size{\sf@size}{0pt}\selectfont A}\kern-.15em\TeX}
\makeatother
\newcommand{\AMSLaTeX}{\protect\AmS-\protect\LaTeX}
\newcommand{\BibTeX}{{\rm B\kern-.05em{\sc
i\kern-.025emb}\kern-.08em\TeX}}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{clm}[thm]{Claim}
\newtheorem{cor}[thm]{Corollary}

\theoremstyle{definition}
\newtheorem{defn}{Definition}
\newtheorem{exmp}{Example}

\newcommand{\PPos} {$P$-position}
\newcommand{\PPoss} {$P$-positions}
\newcommand{\NPos} {$N$-position}
\newcommand{\NPoss} {$N$-positions}

\numberwithin{equation}{section}

\begin{document}

\title[Wythoff's Sequence and N-Heap Wythoff's Conjectures]
{Wythoff's Sequence and N-Heap Wythoff's Conjectures}

\author{Xinyu Sun}
\address{Department of Mathematics, Temple University, Philadelphia, PA 19122}
\email{xysun@math.temple.edu}


%\keywords{Wythoff's Game, Fibonacci sequence}
%\subjclass{00000; Secondary 00000}



\begin{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\} \cup T)$,
$B_n - A_n = n$, and $\{B_n\} \cap T = \emptyset$.
Structural properties and behaviors of Wythoff's sequence are investigated.
The main result is that for such a sequence, there always exists an integer $\alpha$
so that when $n$ is large enough, $|A_n - \lfloor n \phi \rfloor - \alpha| \le 1$,
where $\phi = (1 + \sqrt{5}) / 2$, the golden section. The value of $\alpha$
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 \cite{Fra2003} are proved to be equivalent.
\end{abstract}




\maketitle


\section{ Introduction} \label{sec_intro}

Wythoff's pairs are pairs of integers
$\{(\lfloor n\phi \rfloor, \lfloor n\phi^2 \rfloor)\}_{n \ge 0}$,
where $\phi = (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{center}
\begin{tabular}{c|llllllllllllll}
n                               &  0 &  1 &  2 &  3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11 & 12 & 13	\\ \hline
$A_n = \lfloor n\phi \rfloor$   &  0 &  1 &  3 &  4 &  6 &  8 &  9 & 11 & 12 & 14 & 16 & 17 & 19 & 21	\\ 
$B_n = \lfloor n\phi^2 \rfloor$ &  0 &  2 &  5 &  7 & 10 & 13 & 15 & 18 & 20 & 23 & 26 & 28 & 31 & 34
\end{tabular}
\end{center}


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}}$, \ldots,
which is 1, 2, 3, 5, 8, 13, 21, 34,~\ldots, 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 \cite{Hogg1978}, Horadam \cite{Hora1978}, 
and Silber \cite{Silb1976}.
Other properties, relationships and applications were investigated extensively by numerous people,
whom we are not going to list here.
%	Bergum, Hoggatt \cite{Berg1980},
%	Kimberling \cite{Kimb1995}, 
%	and Silber \cite{Silb1977}, just to name a few.

Wythoff's pairs were first found as the result of a mathematical game \cite{Wyt}:
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 \ge 0}$,
so that $A_n = mex\{A_m,\ B_m\ :\ 0 \le m < n\}$
and $B_n = A_n + n$ with $A_0 = B_0 = 0$, where mex is the {\em M}inimal {\em EX}clusive
value, i.e., the least nonnegative integer that is {\em not} in the set.
The winning strategies were described by Fraenkel \cite{Fra1982}, and also in WW \cite{WW}.
and periodic properties of the Sprague-Grundy function and other generalizations of the game
were also discussed. Please see the manuscript by Fraenkel \cite{Fra2003} for a complete list 
of the progress.
%	was also 
%	proved by Blass and Fraenkel \cite{Bla90}, A. Dress, A. Flammenkamp and N. Pink \cite{Dre},
%	and Landman \cite{Lan}.
%	and generalizations of the game were done by 
%	Fraenkel, Borosh \cite{Fra1973},
%	and Fraenkel, Zusman \cite{Fra2001}.

Another elegant generalization of the game involving more than two piles was proposed by
Fraenkel \cite{Fra2003}, which is also listed by Guy and Nowakowski \cite{Guy} 
as one of the ``unsolved problems in combinatorial games":
given $N$ piles of tokens,  whose sizes are
$A^1, \dots, A^N$, $A^1 \le \dots \le A^N$.
A player can remove any number
of tokens from a single pile, or remove ($a_1$, $\dots$, $a_N$) tokens from all piles --- 
$a_i$ tokens from the $i$-th pile, providing that $0 \le a_i \le A^i$, $\sum_{i=1}^{N}a_i > 0$, 
and $a_1 \oplus \cdots \oplus a_N = 0$, where $\oplus$ is the nim addition (XOR binary operation).
Denote all the \PPoss\ by
$(A^1, \dots, A^{N-2}, A^{N-1}_n, A^{N}_n)$, $A^{N-2} \le A^{N-1}_n \le A^{N}_n$ and
$A^{N-1}_n < A^{N-1}_{n+1}$ for all $n \ge 0$. 
Two conjectures were presented on the game, when $A^1, \dots, A^{N-2}$ are fixed: 

{\em Conjecture 1:} There exists an integer $N_1$ so that
when $n > N_1$, $A^{N}_{n} = A^{N-1}_{n} + n$.

{\em Conjecture 2:} There exist integers $N_2$ and $\alpha_2$ so that
when $n > N_2$, $A^{N-1}_{n} = \lfloor n \phi \rfloor + \epsilon_n + \alpha_2$ and
$A^{N}_{n} = A^{N-1}_{n} + n$, where $-1 \le \epsilon_n \le 1$.

Furthermore, $A^{N-1}_n = mex(\{A^{N-1}_i, A^{N}_i:\ 0 \le i < n\}\ \cup\ T)$, 
where $T$ is a small set of integers.

By preserving the moves related to the nim addition, the winning strategy
of the multiple-heap Wythoff's game seems to have retained the golden section, just as the original game did.
Doron Zeilberger and the author \cite{Sun2003} 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~\ref{sec_wyt_seq},
the basic properties of Wythoff's sequence in section~\ref{sec_wyt_prop},
and special Wythoff's sequence and the equivalency of the two conjectures
on $N$-heap Wythoff's game in section~\ref{sec_wyt_conj}.

\section{Wythoff's Sequence} \label{sec_wyt_seq}

\begin{defn} \label{def_ws}
We call a sequence of pairs of integers $\{(A_n, B_n)\}_{n \ge n_0}$ a {\em Wythoff's sequence}
if there exist a finite set of integers $T$ so that
$A_n = mex(\{A_i, B_i: n_0 \le i < n\} \cup T)$, $B_n = A_n + n$ 
and $\{B_n\} \cap T = \emptyset$. 
\end{defn}

\begin{defn} \label{def_sws}
A {\em special Wythoff's sequence} is a Wythoff's sequence
such that there exist integers $N$ and $\alpha$ so that when $n > N$,
$A_n = \lfloor n\phi \rfloor + \alpha + \epsilon_n$,
where $\epsilon_n \in \{0, \pm 1\}$.
\end{defn}

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.

\begin{thm} \label{thm_con}
$\{(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 \subset \mathbb{Z}_{\ge 0}$,
so that
$A_n = mex(\{A_i, B_i : i < n \} \cup S_1)$, 
$B_n = mex\{ \{A_n + B_i - A_i : i < n \} \cup \{ A_n + t : t \in S_2 \} \cup S_1 \}$.
%	then $\exists N$ so that when $n \ge N$, $B_n - A_n - n$ is a constant, i.e., 
In such a case, $S_2 = \mathbb{Z}_{\ge 0} - \{B_i - A_i : i > 0\}$.
\end{thm}

Proof: Given $S_1$ and $S_2$ are as described above, there  exists $N_0$
so that when $n \ge N_0$, $A_n > \max(S_1)$ and 
$B_n - A_n > \max(S_2)$. Denote $\alpha_n = \max\{B_i - A_i : i < n \} + 1$
and $D_n = \{i : 0 \le i < \alpha_n \} - S_2 - \{B_i - A_i : i < n\}$.
Then for any $n \ge N_0$, it is obvious that $B_n - A_n \le \alpha_n$.
Now $B_n - A_n < \alpha_n$ iff $B_n - A_n \in D_n$; 
iff $\alpha_{n+1} = \alpha_n$; iff $D_{n} = D_{n+1} \cup \{B_n - A_n\}$.
Also, $B_n - A_n = \alpha_n$ iff $\alpha_{n+1} = \alpha_n + 1$; iff $D_{n+1} = D_n$.
Note that $D_{n+1} \subset D_n \subset D_{n_0}$ are all finite, so there exists $N \ge N_{0}$
such that for any $n \ge N$, $D_n = D_{n+1}$,
and $B_{n+1} - A_{n+1} = \alpha_{n+1} = \alpha_n + 1 = B_n - A_n + 1$.

Now supposedly there exists $d \in \mathbb{Z}_{\ge 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 \ref{lem_ws} 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 \ref{def_ws}. 

Conversely, if $\{(A_n, B_n)\}$ is a Wythoff's sequence, we can define
$S_1 = \mathbb{Z}_{\ge 0} - \{A_i, B_i : i > 0\}$ and 
$S_2 = \mathbb{Z}_{\ge 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\} \cap S_1 = \emptyset$ and $\{B_n - A_n\} \cap S_2 = \emptyset$,
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.

\section{Properties of Wythoff's Sequence} \label{sec_wyt_prop}

From this section and on, for any Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$,
we always assume that when $n \ge n_0$, $A_{n_0} > max(T)$ as in Definition  \ref{thm_con};
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 \ref{thm_con}.
Otherwise, we can always increase the value of $n_0$.

\begin{lem} \label{lem_ws}
Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$,
\begin{enumerate}
\item $1 \le A_{n+1} - A_n \le 2$,
\item $2 \le B_{n+1} - B_n \le 3$, and
\item $|\lfloor n_1\phi \rfloor - \lfloor n_2\phi \rfloor - (n_1 - n_2)\phi| < 1$.
\end{enumerate}
\end{lem}

Proof: See \cite{Sun2003}.

\begin{thm} \label{thm_bp}
Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge 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$.
\end{thm}

Proof: By lemma \ref{lem_ws}, 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 + 2 n_0 - 2 = 2 n_0 - 2 - c$.

Now for any $n \ge 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 + 2 n_0 - 2 - (2 n_0 - 2 - c)
= B_n + c - 1$.
By Lemma~\ref{lem_ws} 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$.


\begin{cor} \label{cor_prop}
Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$ and $c$ as in Theorem \ref{thm_bp}, \\
$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$.
\end{cor}

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} \ge B_{m_2}$
and we know $\{(A_n, B_n) : m_2 \le n \le 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:

\begin{enumerate}
\item For any $m > m_1$, by Theorem \ref{thm_bp}, 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'$.
\item If $A_{m}$ is known and if $m - c$ is in the A's, by Corollary \ref{cor_prop},
	$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 \ge m_2}$ or $\{B_n\}_{n \ge m_2}$ without
	any	knowledge of the other.
\end{enumerate}

\begin{cor} \label{cor_nab}
Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$, then for any $n \ge A_{n_0}$,
the number of $A$'s less than $n$ is $A_{n+c} - n - n_0 + 1$; for any $n \ge B_{n_0}$,
the number of $B$'s less than $n$ is $2n - A_{n+c} + c - n_0$.
\end{cor}

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 \ref{cor_prop},
$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 \cite{Hogg1978}, 
Hoggatt, Bicknell-Johnson \cite{Hogg1982}, and Silber \cite{Silb1976}.



\section{Special Wythoff's Sequence and $N$-heap Wythoff's Conjectures} \label{sec_wyt_conj}

Throughout this section we use Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$ and $c$ 
as in Theorem~\ref{thm_bp}.
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} \pm 1$ and $B_m = A_{m_2} + 1$,
so $n$ must be of the form
$B_{A_m + c + \epsilon_2} + c + \epsilon_1$, where $\epsilon_1 \in \{-1, 0, 1\}$
and $\epsilon_2 \in \{0, 1\}$.


\begin{thm} \label{thm_spec}
Every Wythoff's sequence is special.
\end{thm}

Proof: Denote  $\alpha_n = A_n - \lfloor n \phi \rfloor$.
We only need to prove that as $m$ and $n$ grow,
$|\alpha_m - \alpha_n|$ eventually decreases to at most 2.

By Corollary \ref{cor_prop}, $A_{B_n + c + 1} - A_{B_n + c} - \phi = 1 - \phi$ and 
$A_{B_n + c - 1} - A_{B_n + c} + \phi = -2 + \phi$, 
so $A_{B_n + c + \epsilon} - A_{B_n + c} - \phi \epsilon 
= (3 \epsilon - 2\phi \epsilon - \epsilon^2)/2$ when $|\epsilon| \le 1$.
Therefore  if we denote $\gamma = 
(A_{B_m + c + \epsilon_m} - A_{B_m + c} - \phi \epsilon_m) -
(A_{B_n + c + \epsilon_n} - A_{B_n + c} - \phi \epsilon_n)$,
$|\gamma|$
$= |(\epsilon_m - \epsilon_n) (3 - 2\phi - \epsilon_m - \epsilon_n) / 2|$
$\le \phi - 1$, when $|\epsilon_m|$, $|\epsilon_n| \le 1$. 
Also note that $A_{A_n + c + \epsilon} - A_{A_n + c} = 2 \epsilon$,
when $\epsilon \in \{0, 1\}$.

We also adopt the following notations:
$\beta_1 = \lfloor (B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}) \phi \rfloor
		- \lfloor (B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}) \phi \rfloor
		- ((B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}) \phi
		- (B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}) \phi)$
and
$\beta_2 = \lfloor m \phi \rfloor - \lfloor n \phi \rfloor
		- (m - n) \phi$.


Now if $\epsilon_{1m}, \epsilon_{1n} \in \{-1, 0, 1\}$ and
$\epsilon_{2m}, \epsilon_{2n} \in \{0, 1\}$,

\begin{tabular}{cl}
	&	$\alpha_{B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}}
		- \alpha_{B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}}$					\\ [2mm]
=	&	$A_{B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}}
		- A_{B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}}$						\\ [2mm]
	&	$- (\lfloor (B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}) \phi \rfloor
		- \lfloor (B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}) \phi \rfloor)$	\\ [2mm]
=	&	$A_{B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}}
		- A_{B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}}$						\\ [2mm]
	&	$- ( (B_{A_m + c + \epsilon_{2m}} - B_{A_n + c + \epsilon_{2n}}) \phi
		+ (\epsilon_{1m} - \epsilon_{1n}) \phi + \beta_1)$							\\ [2mm]
=	&	$A_{B_{A_m + c + \epsilon_{2m}} + c}
		- A_{B_{A_n + c + \epsilon_{2n}} + c} + \gamma
		- (B_{A_m + c + \epsilon_{2m}} - B_{A_n + c + \epsilon_{2n}}) \phi
		- \beta_1$																	\\ [2mm]
=	&	$A_{A_m + c + \epsilon_{2m}} - A_{A_n + c + \epsilon_{2n}}
		+ (B_{A_m + c + \epsilon_{2m}} - B_{A_n + c + \epsilon_{2n}})(1 - \phi)
		 + \gamma - \beta_1$														\\ [2mm]
=	&	$(A_{A_m + c + \epsilon_{2m}} - A_{A_n + c + \epsilon_{2n}})(2 - \phi)
		+ (A_m - A_n + \epsilon_{2m} - \epsilon_{2n})(1 - \phi) + \gamma - \beta_1$	\\ [2mm]
=	&	$(A_{A_m + c} - A_{A_n + c} + 2(\epsilon_{2m} - \epsilon_{2n}))(2 - \phi)
		+ (A_m - A_n + \epsilon_{2m} - \epsilon_{2n})(1 - \phi)
		 + \gamma - \beta_1$														\\ [2mm]
=	&	$(A_{A_m + c} - A_{A_n + c})(2 - \phi)
		+ (A_m - A_n)(1 - \phi) + (\epsilon_{2m} - \epsilon_{2n})(5 - 3\phi)
		 + \gamma - \beta_1$														\\ [2mm]
\end{tabular}


\begin{tabular}{cl}
=	&	$(B_m - B_n)(2 - \phi)
		+ (A_m - A_n)(1 - \phi) + (\epsilon_{2m} - \epsilon_{2n})(5 - 3\phi)
		 + \gamma - \beta_1$														\\ [2mm]
=	&	$(A_m - A_n)(3 - 2\phi) + (m - n)(2 - \phi)
		+ (\epsilon_{2m} - \epsilon_{2n})(5 - 3\phi) + \gamma - \beta_1$			\\ [2mm]
=	&	$(\lfloor m \phi \rfloor + \alpha_m - \lfloor n \phi \rfloor
		- \alpha_n)(3 - 2\phi) + (m - n)(2 - \phi)
		+ (\epsilon_{2m} - \epsilon_{2n})(5 - 3\phi) + \gamma - \beta_1$			\\ [2mm]
=	&	$((m - n) \phi + \beta_2 + (\alpha_m - \alpha_n))(3 - 2\phi)
		+ (m - n)(2 - \phi)$														\\ [2mm]
	&	$+ (\epsilon_{2m} - \epsilon_{2n})(5 - 3\phi) + \gamma - \beta_1$			\\ [2mm]
=	&	$-(\alpha_m - \alpha_n))(2\phi - 3) - \beta_2(2\phi - 3)
		+ (\epsilon_{2m} - \epsilon_{2n})(5 - 3\phi) + \gamma - \beta_1.$			\\ [2mm]
\end{tabular}


\begin{tabular}{cl}
So	&	$|\alpha_{B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}}
		- \alpha_{B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}}|$				\\ [2mm]
$\le$	&	$|\alpha_m - \alpha_n|(2\phi - 3) + |\beta_2|(2\phi - 3)
			+ |\epsilon_{2m} - \epsilon_{2n}|(5 - 3\phi) + |\gamma| + |\beta_1|$	\\ [2mm]
$<$		&	$|\alpha_m - \alpha_n|(2\phi - 3) +
			(2\phi - 3) + (5 - 3\phi) + \phi - 1 + 1$								\\ [2mm]
$=$		&	$|\alpha_m - \alpha_n|(2\phi - 3) + 2.$									\\ [2mm]
\end{tabular}

Since it is an integer,
$|\alpha_{B_{A_m + c + \epsilon_{2m}} + c + \epsilon_{1m}}
- \alpha_{B_{A_n + c + \epsilon_{2n}} + c + \epsilon_{1n}}|
\le \max(|\alpha_m - \alpha_n| - 1, 2)$.
%	Therefore for any $k$, 
%	if we denote $k_1 = B_{A_{k} + c + 1} + 1$, $k_2 = B_{A_{k_1+1} + c + 1} + 1$ 
%	and $\delta = \max\{|\alpha_{m_1} - \alpha_{m_2}| : k \le m_1, m_2 \le k_1\}$,
%	then $\max\{|\alpha_{m_1} - \alpha_{m_2}| : k_1 + 1 \le m_1, m_2 \le k_2\} 
%	\le \max(\delta - 1, 2)$. 
So for any integers $m$ and $n$, we can construct two sequences $a_1, \ldots , a_k$
and $b_1, \ldots , b_k$, such that $a_k = m$, $b_k = n$,
$a_i = B_{A_{a_{i-1}}+ c + \epsilon_{a2i}}  + \epsilon_{a1i}$ and $b_i = B_{A_{b_{i-1}} + c  + \epsilon_{b2i}}  + \epsilon_{b1i}$,
where $1 < i \le k$,  $\epsilon_{a1i}, \epsilon_{b1i} \in \{0, \pm1\}$ and $\epsilon_{a2i}, \epsilon_{b2i} \in \{0, 1\}$.
Then when $k$ is large enough, i.e., when $m$ and $n$ are large enough,
$|\alpha_{a_i} - \alpha_{b_i}|$ decreases to at most 2.



Using the same method, we can investigate the behavior of the sequence 
$\{\alpha_m\}_{m \ge n_0}$:

Denote $\beta_3 = (\lfloor A_m \phi \rfloor - \lfloor A_n \phi \rfloor) - (A_m - A_n) \phi$,
and $\beta_4 = (\lfloor m \phi \rfloor - \lfloor n \phi \rfloor) - (m - n) \phi$.

\begin{tabular}{cl}
	&	$\alpha_{A_m} - \alpha_{A_n}$												\\ [2mm]
=	&	$A_{A_m} - A_{A_n} - (\lfloor A_m \phi \rfloor - \lfloor A_n \phi \rfloor)$	\\ [2mm]
=	&	$B_m - B_n - (A_m - A_n) \phi - \beta_3$									\\ [2mm]
=	&	$(A_m - A_n)(1 - \phi) + (m - n) - \beta_3$									\\ [2mm]
=	&	$(\lfloor m \phi \rfloor - \lfloor n \phi \rfloor
			+ \alpha_m - \alpha_n)(1 - \phi) + (m - n) - \beta_3$					\\ [2mm]
=	&	$(m - n) \phi + \beta_4 + \alpha_m - \alpha_n)(1 - \phi) 
			+ (m - n) - \beta_3$													\\ [2mm]
=	&	$-(\alpha_m - \alpha_n)(\phi - 1) - \beta_3 - \beta_4 (\phi - 1)$.			\\ [2mm]
\end{tabular}


So when $|\alpha_m - \alpha_n| \ge 3$, $(\alpha_{A_m} - \alpha_{A_n})$ and
$(\alpha_m - \alpha_n)$ always have different signs.
Together with the fact that $|\alpha_{m+1} - \alpha_m| = |A_{m+1} - A_m -
(\lfloor (m+1) \phi \rfloor - \lfloor m \phi \rfloor)| \le 1$, let us consider
$\alpha(m) = \alpha_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 \ref{thm_spec}, the amplitude
eventually decreases to 1, when the oscillation of the graph becomes somewhat unpredictable.

\begin{lem}
In the two conjectures on the $N$-heap Wythoff's game, 
$A^{N-1}_n = mex(\{A^{N-1}_i, \\ 
A^{N}_i : \ 0 \le i < n\}\ \cup\ T)$,
where $T$ is a finite set depending only on $A^1, \ldots, A^{N-2}$.
In fact, $T = \{a : \exists b \le A^{N-2}$ and $k \le N-2$,
	such that $A^{k-1} \le b \le A^{k}$ 
	and $(A^1, \ldots, A^{k-1}, b, A^{k}, \ldots, A^{N-2}, \\
	a)$ is a \PPos\}.
\end{lem}

Proof: By definition, $T = \mathbb{Z}_{\ge 0} - \{A^{N-1}_i, A^{N}_i:\ i > 0\}$.
Denote $T'$ as the last set in the lemma. We claim $T = T'$. First, $T' \subset T$
because for any $b \ge a$, $(A^1, \ldots, A^{N-2}, a, b)$ is an \NPos{}
since we can remove tokens from the last pile to create a \PPos;
and similar argument can be applied when $A^{N-2} < b < a$.

For any $a \in T$ and $b \ge a$, $(A^1, \ldots, A^{N-2}, a, b)$ is an \NPos{}
by the definition of $T$.
There are several kind of moves from this position to create a \PPos:

\begin{enumerate}
\item	Remove $a_1, \ldots, a_N$ tokens from all corresponding piles,
		where $a_1 \oplus \cdots \oplus a_N = 0$,
		so that $(A^1 - a_1, \ldots, A^{N-2} - a_{N-2}, a - a_{N-1}, b - a_N)$ is a \PPos.
\item	Remove $a_k \le A^k$ tokens from the $k$-th pile,
		so that $(A^1, \ldots, A^{k-1}, A^k - a_k, \\
		A^{k+1}, \ldots, A^{N-2}, a, b)$ is a \PPos;
\item	Remove $a_{N-1} \le a$ tokens from the $(N-1)$-th pile,
		so that $(A^1, \ldots, A^{N-2}, a - a_{N-1}, b)$ is a \PPos;
\item	Remove $a_{N} \le b$ tokens from the $N$-th pile,
		so that $(A^1, \ldots, A^{N-2}, a, b - a_{N})$ is a \PPos;
\end{enumerate}

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, \ldots, A^{N-2}, a, b - b')$ is a \PPos.
Again by the definition of $T$ and by the convention that we adopted:
$A^1 \le \cdots \le A^{N-2} \le a \le b$, we must have $b - b' \le A^{N-2}$,
which shows $T \subset T'$.
$T'$ is obviously finite, since $A^1 \le \cdots \le A^{N-2}$ are finite.

Now denote $a = mex(\{A^{N-1}_i, A^{N}_i : \ 0 \le i < n\}\ \cup\ T)$.
It is obvious that $A^{N-1}_n \ge a$.
Also, by the definition of $T$ and mex,
$(A^1, \ldots, A^{N-2}, c, a)$ is an \NPos for any $A^{N-2} \le c < a$,
but there must exist an integer $b \ge a$ such that $(A^1, \ldots, A^{N-2}, a, b)$ is a \PPos.
Finally, since we assume $A^{N-1}_{n-1} < A^{N-1}_{n}$,
if there exists $b$ such that $A^{N-1}_{n-1} < b < A^{N-1}_{n}$,
we must have either $b \in T$ or $b \in \{A^{N}_i\}_{i \ge 1}$.
Combining all the arguments above, $a = A^{N-1}_n$.



\begin{cor} \label{cor_eqv}
The two conjectures on the $N$-heap Wythoff's game are equivalent.
\end{cor}

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 \ref{thm_spec}.


\begin{thm}
Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$ and $\alpha$ are as in 
Definition~\ref{def_sws}, $\alpha = -c$.
\end{thm}

Proof: Denote $\beta_5 = \lfloor (A_{n} + c) \phi \rfloor - (A_{n} + c) \phi$
and $\beta_6 = \lfloor n \phi \rfloor - n \phi$.
Then $A_n + n - 1 = B_n - 1 = A_{A_n + c}
= \lfloor (A_{n} + c) \phi \rfloor + \alpha + \epsilon_{A_n+c}
= A_n \phi + c \phi + \alpha + \epsilon_{A_n+c} + \beta_5$. 
So $\epsilon_{A_n+c} + \beta_5 = A_n (1 - \phi) - 1 + n - c \phi - \alpha
= (n \phi + \alpha + \epsilon_n + \beta_6)(1 - \phi) + n - c \phi - \alpha - 1
= -(c + \alpha) \phi + (\epsilon_n + \beta_6)(1 - \phi) - 1$,
hence $-(c + \alpha) \phi
= \epsilon_{A_n+c} + \beta_5 + (\epsilon_n + \beta_6)(\phi - 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 $\phi$. Note that $-1 < \beta_5, \beta_6 < 0$,
and $\epsilon_{A_n+c}, \epsilon_n \in \{0, \pm 1\}$,
therefore the proof is completed if we can find an integer $N$ so that
%\begin{displaymath}
\begin{eqnarray}
\epsilon_{A_N+c} = 0;									&	or	\label{cond_1}	\\
\epsilon_{N} = 0\ and\ \epsilon_{A_N+c} \in \{0, -1\};	&	or	\label{cond_2}	\\
\epsilon_{N} = -1\ and\ \epsilon_{A_N+c} \in \{0, 1\}.			\label{cond_3}
\end{eqnarray}
%\end{displaymath}

First we can assume $\epsilon_{n}$ is not a constant, otherwise we can adjust the value
of $\alpha$ so that $\epsilon_{n}$ is always 0. Secondly, 
since $|\epsilon_{n}| \le 1$ and
$|\epsilon_{n} - \epsilon_{n-1}| \le
|(A_n - A_{n-1}) - (\lfloor n \phi \rfloor - \lfloor (n - 1) \phi \rfloor)| \le 1$,
there always exists an $n$ large enough so that $\epsilon_{n} = 0$.
By the condition \ref{cond_2} above, we only have to consider the case
for when $\epsilon_{n} = 0$ and $\epsilon_{A_n+c} = 1$.
From now on, we always assume $n$ is large enough.


If $A_n = A_{n-1} + 1$, by Corollary~\ref{cor_prop}, there exist $m$ so that
$n = B_m + 1 + c$; and by Lemma~\ref{lem_ws},
there exists $m'$ so that $B_m + 1 = A_{m'}$.
Therefore, $\epsilon_{A_{m'}+c} = \epsilon_n = 0$, which
proves the theorem by choosing $N = m'$ and using condition~\ref{cond_1}.


If $A_n = A_{n-1} + 2$,
$3 \le \lfloor (A_n + c) \phi \rfloor - \lfloor (A_{n-1} + c) \phi \rfloor \le 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 \ref{cor_prop},
which means $\lfloor (A_n + c) \phi \rfloor - \lfloor (A_{n-1} + c) \phi \rfloor
+ \epsilon_{A_n+c} - \epsilon_{A_{n-1}+c} = 3$.
Therefore $\lfloor (A_n + c) \phi \rfloor - \lfloor (A_{n-1} + c) \phi \rfloor = 3$
and $\epsilon_{A_{n-1}+c} = 1$, because of our assumption of $\epsilon_{A_n+c} = 1$.
Since $2 = A_n - A_{n-1} = \lfloor n \phi \rfloor - \lfloor (n-1) \phi \rfloor
- \epsilon_{n-1}$, we have either
$\lfloor n \phi \rfloor - \lfloor (n-1) \phi \rfloor = 1$ and $\epsilon_{n-1} = -1$,
or $\lfloor n \phi \rfloor - \lfloor (n-1) \phi \rfloor = 2$ and $\epsilon_{n-1} = 0$.
In the former case we have proved the theorem by choosing $N = n-1$
and using condition~\ref{cond_3} because $\epsilon_{n-1} = -1$ and $\epsilon_{A_{n-1}+c} = 1$;
while in the latter case $\epsilon_{A_{m} + c} = \epsilon_{n-1} = 0$,
so we can choose $ N = m$ and use condition~\ref{cond_1}.


The theorem indicates that the value of $\alpha$ 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~\ref{thm_bp}, 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~\ref{cor_nab}, 
$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.




\section{Remarks and Acknowledgements} \label{sec_conc}

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

Lemma \ref{lem_ws} and Corollary \ref{cor_eqv}, 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.


\makeatletter \renewcommand{\@biblabel}[1]{\hfill#1.}\makeatother

\begin{thebibliography}{2}

%\bibitem{Bla90} U. Blass and A. S. Fraenkel, The Sprague-Grundy function for Wythoff's game,
%   {\em Theoret. Comp. Sci.} \textbf{75} (1990) 311--333.

%\bibitem{Berg1980} G. E. Bergum and V. E. Hoggatt, Jr., 
%	Some extensions of Wythoff pair sequences. 
%	{\em Fibonacci Quart.} \textbf{18} (1980) 28--33.

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

%\bibitem{Dre} A. Dress, A. Flammenkamp and N. Pink, Additive periodicity of the 
%    Sprague-Grundy function of certain Nim games, 
%    {\em Adv. in Appl. Math.} \textbf{22} (1999) 249--270.

\bibitem{Fra2003} A. S. Fraenkel, Complexity, appeal and challenges of combinatorial Games,
    to appear in {\em Theoret. Comp. Sci.}, special issue on 
    Algorithmic Combinatorial Game Theory.

\bibitem{Fra1982} A. S. Fraenkel, How to beat your Wythoff games' opponent on three fronts,
    {\em Amer. Math. Monthly} \textbf{89} (1982) 353--361.

%\bibitem{Fra1973} A. S. Fraenkel and I. Borosh, A generalization of Wythoff's
%    game, {\em J. Combin. Theory} (Ser. A) \textbf{15} (1973) 175--191.
        
%\bibitem{Fra2001} A. S. Fraenkel and D. Zusman, A new heap game,
%    {\em Theoret. Comput. Sci.} \textbf{252} (2001) 5--12, 
%    special ``Computers and Games" issue.
        
\bibitem{Guy} R. K. Guy and R. J. Nowakowski, Unsolved problems in combinatorial games,
    in: {\em More Games of No Chance}, Cambridge University Press, Cambridge, 2002, 457--473.

\bibitem{Hogg1982} V. E. Hoggatt, Jr. and M. Bicknell-Johnson, 
	Sequence transforms related to representations using generalized
	Fibonacci numbers. {\em Fibonacci Quart.} \textbf{20} (1982) 289--298.

\bibitem{Hogg1978} V. E. Hoggatt, Jr.; A. P. Hillman, A property of Wythoff pairs. 
	{\em Fibonacci Quart.} \textbf{16} (1978) 472.

\bibitem{Hora1978} A. F. Horadam, 
	Wythoff pairs. {\em Fibonacci Quart.} \textbf{16} (1978) 147--151.

%\bibitem{Kimb1995} C. Kimberling, The Zeckendorf array equals the Wythoff array. 
%	{\em Fibonacci Quart.} \textbf{33} (1995) 3--8.

%\bibitem{Lan} H. Landman, A simple FSM-based proof of the additive periodicity
%	of the Sprague-Grundy function of Wythoff's game, in:
%	{\em More Games of No Chance}, Cambridge University Press, Cambridge, 2002, 383--386.

%\bibitem{Silb1977} R. Silber, Wythoff's Nim and Fibonacci representations. 
%	{\em Fibonacci Quart.} \textbf{15} (1977) 85--88.

\bibitem{Silb1976} R. Silber, A Fibonacci property of Wythoff pairs. 
	{\em Fibonacci Quart.} \textbf{14} (1976) 380--384. 

\bibitem{Sun2003} X. Sun and D. Zeilberger, 
	On Fraenkel's $N$-heap Wythoff's conjecture, preprint.

\bibitem{Wyt} W. A. Wythoff, A modification of the game of Nim, 
	{\em Nieuw Arch. Wisk.} \textbf{7} (1907) 199--202.


\end{thebibliography}


\end{document}



