\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, Wythoff's sequence, Special Wythoff's 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}$ such 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$ such 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 removing 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}$, such 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}. 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 the 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 in the survey article 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$ such that when $n > N_1$, $A^{N}_{n} = A^{N-1}_{n} + n$. {\em Conjecture 2:} There exist integers $N_2$ and $\alpha_2$ such 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 $n_0 > 0$ and there exist a finite set of integers $T$ such 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$ such 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 > 0$ 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}$, such 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$ such 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} \begin{proof} Given $S_1$ and $S_2$ are as described above, there exists $N_0$ such that when $n \ge N_0$, $A_n > \max(S_1)$ and $B_n - A_n > \max(S_2)$. If we write $\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$ and $\alpha_n \le \alpha_{n+1}$. 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$. 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. For the last part of the theorem, observe that $S_2 \subset \mathbb{Z}_{\ge 0} - \{B_i - A_i : i > 0\}$ by the definition of $B_n$. If there exists $d \in \mathbb{Z}_{\ge 0} - \{B_i - A_i : i > 0\} - S_2$, $B_n \neq A_n + d$ for all $n$. When $n$ is large enough such that $B_i - A_i > d$ for all $i \ge n$, there exists $m < n$ such that $A_n + d = B_m$ for each $n$, since ever large integer has to be an $A$ or $B$, and $\{A_i\}$ is an ascending sequence when $i$ is large enough by the definitions. Therefore for any $n$ large enough, there exist $m_1$ and $m_2$ such 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}. \end{proof} So even though we can start with two random finite sets of integers, $S_1$ and $S_2$, such 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 using {\it mex} 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$ and the sizes of $T$, $S_1$ and $S_2$ by eliminating the early entries of the sequence. \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} \begin{proof} See \cite{Sun2003}. \end{proof} \begin{thm} \label{thm_bp} Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$, there exists a constant $c$, such 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} \begin{proof} By lemma \ref{lem_ws}, there exists $k_0$ such 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$. Let $c = k_0 - A_{n_0}$. We now 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$. So $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$. \end{proof} \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} \begin{proof} $A_{m + c + 1} - A_{m + c} = 2$ iff there exists $n$, such 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. \end{proof} Notice that if there exist $m_1 > m_2 > n_0$ such 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} \begin{proof} Let $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 proved. 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$. \end{proof} 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} \begin{proof} Let $\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 write $\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 notation: $\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] \end{tabular} \begin{tabular}{cl} = & $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] = & $(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)$. Now 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_{n_0} \le \min(a_1, b_1) < B_{A_{n_0}+ c + 1} + 1$, and $a_i = B_{A_{a_{i-1}}+ c + \epsilon_{a2i}} + \epsilon_{a1i}$, $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\}$. Hence if $\max(|\alpha_i - \alpha_j| : i, j \ge 1) = N$ is finite, then when $k \ge N$, or equivalently when $m$ and $n$ are large enough, $|\alpha_m - \alpha_n| = |\alpha_{a_k} - \alpha_{b_k}|$ decreases to at most 2. The assumption is proved in the following lemma, which completes our proof. \end{proof} \begin{lem} \label{lem_bound} $\alpha_n$ is bounded for all $n$. \end{lem} \begin{proof} %Using the same method, we can investigate the behavior of the sequence %$\{\alpha_m\}_{m \ge n_0}$: Let $\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] \end{tabular} \begin{tabular}{cl} = & $((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} Define $\delta_0 = 1$ and $\delta_i = 1 - (\phi - 1) \delta_{i-1}$ recursively for $i \ge 1$. %Now if we write $\delta_i = a_i - b_i \phi$, %then $a_0 = 1$, $b_0 = 0$ and $a_1 = 2$. %Also since $\delta_{i+1} = 1 - (\phi - 1) \delta_{i} %= 1 - (\phi - 1)(a_i - b_i \phi) %= 1 - a_i \phi + a_i + b_i \phi^2 - b_i \phi %= a_i + b_i + 1 - a_i \phi$, so $b_{i+1} = a_i$ and $a_{i+1} = a_i + a_{i-1} + 1$. %If we write $F_n$ as the Fibonacci numbers with $F_0 = F_1 = 1$, %we claim that $a_n = F_{n+2} - 1$. We know that $a_0 = 1 = F_2 - 1$, %$a_1 = 2 = F_3 - 1$, so by induction %$a_{n+1} = a_n + a_{n-1} + 1 = F_{n+2} - 1 + F_{n+1} - 1 + 1 = F_{n+3} - 1$. %It is well known that $F_n = (\phi^{n+1} - (1-\phi)^{n+1}) / \sqrt{5}$, %therefore $\delta_n = F_{n+2} - F_{n+1} \phi - 1 + \phi %= (\phi^{n+3} - (1-\phi)^{n+3}) / \sqrt{5} % - (\phi^{n+2} - (1-\phi)^{n+2}) \phi / \sqrt{5} + \phi - 1 %= (1-\phi)^{n+2} + \phi - 1$. If we write $\delta_n = (1- \phi)^n g_n$, $g_n = g_{n-1} + 1 / (1 - \phi)^n$, i.e., $g_n = \sum^{n}_{i=1}1 / (1 - \phi)^i = ((1 - \phi)^{n+1} - 1) / (-\phi (1 - \phi)^n)$. So $$\delta_n = (1 - \phi)^n g_n = \phi - 1 + (1 - \phi)^{n+2}.$$ Hence $\delta_n \rightarrow \phi - 1$, as $n \rightarrow \infty$, and $|\delta_n| \le 1$. Note that for any integer $m$, we can construct a sequence $a_1, \ldots , a_k$, such that $a_k = m$, $A_{n_0} \le a_1 < A_{A_{n_0}},\ a_i = A_{a_{i-1}},$ where $1 < i \le k$. Let $\beta^i_3 = (\lfloor a_i \phi \rfloor - \lfloor a_{i-1} \phi \rfloor) - (a_{i} - a_{i-1}) \phi$, and $\beta^i_4 = (\lfloor a_{i-1} \phi \rfloor - \lfloor a_{i-2} \phi \rfloor) - (a_{i-1} - a_{i-2}) \phi = \beta^{i-1}_3$, then $$\alpha_{a_{i}} - \alpha_{a_{i-1}} = -(\alpha_{a_{i-1}} - \alpha_{a_{i-2}}) (\phi - 1) - \beta^i_3 - \beta^i_4,\ 1 < i \le k$$ by the previous result. \begin{tabular}{rl} Now & $\alpha_m$ \\ [2mm] $=$ & $\alpha_{a_1} + \sum_{i=2}^{k} (\alpha_{a_{i}} - \alpha_{a_{i-1}})$ \\ [2mm] $=$ & $\alpha_{a_1} - (\alpha_{a_{k-1}} - \alpha_{a_{k-2}}) (\phi - 1) - \beta^k_3 - \beta^k_4 (\phi - 1) + \sum_{i=2}^{k-1} (\alpha_{a_{i}} - \alpha_{a_{i-1}})$ \\ [2mm] %$=$ & $\alpha_{a_1} + (\alpha_{a_{k-1}} - \alpha_{a_{k-2}}) \delta_1 % - \beta^k_3 - \beta^k_4 (\phi - 1) % + \sum_{i=2}^{k-2} (\alpha_{a_{i}} - \alpha_{a_{i-1}})$ \\ [2mm] $=$ & $\alpha_{a_1} - (\beta^k_3 + \beta^k_4 (\phi - 1)) \delta_0 + (\alpha_{a_{k-1}} - \alpha_{a_{k-2}}) \delta_1 + \sum_{i=2}^{k-2} (\alpha_{a_{i}} - \alpha_{a_{i-1}})$ \\ [2mm] $=$ & $\alpha_{a_1} - (\beta^k_3 + \beta^k_4 (\phi - 1)) \delta_0 - (\beta^{k-1}_3 + \beta^{k-1}_4 (\phi - 1)) \delta_1$ \\ [2mm] & $ + (\alpha_{a_{k-2}} - \alpha_{a_{k-3}}) \delta_2 + \sum_{i=2}^{k-3} (\alpha_{a_{i}} - \alpha_{a_{i-1}})$ \\ [2mm] $=$ & $\cdots$ \\ [2mm] $=$ & $\alpha_{a_1} - \sum^{k}_{i=3}( (\beta^i_3 + \beta^i_4 (\phi - 1)) \delta_{k-i} ) + (\alpha_{a_{2}} - \alpha_{a_{1}}) (\delta_{k-2} + 1)$.% \\ [2mm] %$=$ & $\alpha_{a_1} % - \sum^{k}_{i=3}( (\beta^i_3 % + \beta^{i-1}_3 (\phi - 1)) \delta_{k-i} ) % + (\alpha_{a_{2}} - \alpha_{a_{1}}) (\delta_{k-2} + 1)$. \end{tabular} We also have \begin{tabular}{rl} & $|\sum^{k}_{i=3} ( \beta^i_3 \delta_{k-i} )|$ \\ [2mm] $=$ & $|\sum^{k}_{i=3} ( (\lfloor a_i \phi \rfloor - a_{i} \phi) \delta_{k-i}) - \sum^{k}_{i=3} ((\lfloor a_{i-1} \phi \rfloor - a_{i-1} \phi)) \delta_{k-i} )|$ \\ [2mm] $=$ & $|\sum^{k}_{i=3} ( (\lfloor a_i \phi \rfloor - a_{i} \phi) \delta_{k-i}) - \sum^{k-1}_{i=2} ((\lfloor a_{i} \phi \rfloor - a_{i} \phi)) \delta_{k-i-1} )|$ \\ [2mm] $=$ & $|\sum^{k-1}_{i=3} ( (\lfloor a_i \phi \rfloor - a_{i} \phi) (\delta_{k-i} - \delta_{k-i-1})) + (\lfloor a_k \phi \rfloor - a_{k} \phi) \delta_{0}) - (\lfloor a_{2} \phi \rfloor - a_{2} \phi)) \delta_{k-3} )|$ \\ [2mm] $\le$ & $\sum^{k-1}_{i=3} ( |\lfloor a_i \phi \rfloor - a_{i} \phi| |\delta_{k-i} - \delta_{k-i-1}|) + |(\lfloor a_k \phi \rfloor - a_{k} \phi) \delta_{0}| + |(\lfloor a_{2} \phi \rfloor - a_{2} \phi) \delta_{k-3}|$ \\ [2mm] $<$ & $\sum^{k-1}_{i=3} |\delta_{k-i} - \delta_{k-i-1}| + \delta_{0} + \delta_{k-3}$ \\ [2mm] $=$ & $\sum^{k-1}_{i=3} |(1-\phi)^{k-i+2} - (1-\phi)^{k-i+1}| + \delta_{0} + \delta_{k-3}$ \\ [2mm] \end{tabular} \begin{tabular}{rl} $<$ & $2 \sum^{\infty}_{i=0} (\phi - 1)^{i} + 2$ \\ [2mm] $=$ & $2 \phi + 4$. \end{tabular} Similarly, $|\sum^{k}_{i=3} ( \beta^i_4 (\phi - 1) \delta_{k-i} )|$ has a constant upper bound too, which means $\alpha_m$ is bounded by a value determined only by the values of $\alpha_{a_1}$ and $\alpha_{a_2}$, regardless of the values of $m$ (or $k$). Since there are only finitely many choices of $a_1$ and $a_2$, $\alpha_m$ is bounded for all $m$. %Therefore the same is true for $\alpha_m - \alpha_n$ %for all $m$ and $n$. \end{proof} From the proof of Lemma~\ref{lem_bound}, we can see that 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} \begin{proof} By definition, $T = \mathbb{Z}_{\ge 0} - \{A^{N-1}_i, A^{N}_i:\ i > 0\}$. Write $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 let $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$. \end{proof} \begin{cor} \label{cor_eqv} The two conjectures on the $N$-heap Wythoff's game are equivalent. \end{cor} \begin{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}. \end{proof} \begin{thm} \label{thm_c} 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} \begin{proof} Let $\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 \begin{tabular}{cl} $\epsilon_{A_n+c} + \beta_5$ & $= A_n (1 - \phi) - 1 + n - c \phi - \alpha$ \\[2mm] & $= (n \phi + \alpha + \epsilon_n + \beta_6)(1 - \phi) + n - c \phi - \alpha - 1$ \\[2mm] & $= -(c + \alpha) \phi + (\epsilon_n + \beta_6)(1 - \phi) - 1,$ \end{tabular} \noindent hence \begin{tabular}{cl} $-(c + \alpha) \phi$ & $= \epsilon_{A_n+c} + \beta_5 + (\epsilon_n + \beta_6)(\phi - 1) + 1.$ \end{tabular} 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 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$ such that $n = B_m + 1 + c$; and by Lemma~\ref{lem_ws}, there exists $m'$ such 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$ such 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 can prove 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}. \end{proof} Theorem~\ref{thm_bp}, together with the comments at the end of the section~\ref{sec_wyt_prop}, indicates that any Wythoff's sequence is ``shifted'' Wythoff pairs. It also maintains the relationship with the golden section with another ``shift'' $\alpha$ and some ``controlled error'' $\epsilon$. Theorem~\ref{thm_c} tells us the values of the two shifts are in fact the same. The fact can be seen from the following example: Given any integer $a$, consider the sequence $\{ (A_n = \lfloor n \phi \rfloor + a, B_n = \lfloor n \phi \rfloor + n + a)\}$, with $n$ large enough. The sequence obviously is a special Wythoff's sequence with $\alpha = a$, because it is generated from the Wythoff's pairs. At the mean time, $A_{A_n - a} = A_{\lfloor n \phi \rfloor} = \lfloor \lfloor n \phi \rfloor \phi \rfloor + a = \lfloor n \phi \rfloor + n - 1 + a = B_{n} - 1$, where the equation in the middle can be derived from the fact that the constant $c$ for the Wythoff's pairs is 0, or from \cite{Berg1980}. Similarly, $A_{B_n - a} = A_{\lfloor n \phi \rfloor + n} = \lfloor (\lfloor n \phi \rfloor + n) \phi \rfloor + a = 2 \lfloor n \phi \rfloor + n + a = A_n + B_n - a$. So the constant $c$ for the sequence is $-a = -\alpha$. To determine the value of $\alpha$ for any Wythoff's sequence, instead of calculating a large number of pairs of integers as the definition requires, we only need the pairs 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$ such that $A_k = B_{n_0} - 1$, which is to find all the $A$'s less than $B_{n_0}$. So by using the notation 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 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, to appear in {\em Ann. Comb.} \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}