\documentclass[12pt]{amsart} \usepackage{amsfonts,amsmath,amstext,amsbsy,euscript,amssymb, graphicx} \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} \theoremstyle{definition} \newtheorem{defn}{Definition} \newtheorem{exmp}{Example} \newcommand{\PPos} {$P$-position} \newcommand{\PPoss} {$P$-positions} \newcommand{\NPos} {$N$-position} \newcommand{\NPoss} {$N$-positions} \newcommand{\MaxResult} {10} \newcommand{\nimp} {\mathit{p}} \numberwithin{equation}{section} \begin{document} \title[On Fraenkel's N-Heap Wythoff's Conjectures] {On Fraenkel's N-Heap Wythoff's Conjectures} \author{Xinyu Sun} \address{Department of Mathematics, Temple University, Philadelphia, PA 19122} \email{xysun@math.temple.edu} \author{Doron Zeilberger} \address{Department of Mathematics, Rutgers University, Piscataway, NJ 08854} \email{zeilberg@math.rutgers.edu} \keywords{Wythoff's Game} \subjclass{91A46; Secondary 68R05} \begin{abstract} The $N$-heap Wythoff's game is a two-player impartial game with $N$ piles of tokens of sizes $A^1, \dots, A^N$, $A^1 \le \dots \le A^N$. Players take turns removing any number of tokens from a single pile, or removing ($a_1$, $\dots$, $a_N$) 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 \dots \oplus a_N = 0$, where $\oplus$ is the nim addition. The first player that cannot make a move loses. Denote all the \PPoss{} (i.e., losing positions) 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 1$. Two conjectures were proposed on the game by Fraenkel \cite{Fra2003}. When $A^1, \dots, A^{N-2}$ are fixed, i) there exists an integer $N_1$ such that when $n > N_1$, $A^{N}_{n} = A^{N-1}_{n} + n$. ii) 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$ and $\phi = (1+\sqrt{5})/2$, the golden section. In this paper, we provide a sufficient condition for the conjectures to hold, and subsequently prove them for the three-heap Wythoff's game with the first piles having up to \MaxResult\ tokens. \end{abstract} \maketitle \section{ Introduction} An impartial game in the normal play is a game in which two players take turns making moves, and the first player who cannot make a move loses. All the information about the game must be available to both players (e.g., unlike most popular card games); all moves must be accessible to both of them; and there is no chance moves (e.g., no dice); and the outcome must be win or lose. Under the assumption of "perfect play" (the two players are infinitely smart), we say that a position is a \PPos{} if the player who makes the {\em previous} move will win, otherwise it is an \NPos{}, i.e., the {\em next} player will win. Wythoff's Game \cite{Wyt} is an impartial game consisting of two piles of tokens. Players can remove any number of tokens from a single pile, or the same number of tokens from both piles. The \PPoss{} are well-known and well explained by Fraenkel \cite{Fra1982}: they are a sequences of pairs of integers $\{(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 not in the set. They can also be written as $A_n = \lfloor n\phi \rfloor$ and $B_n = \lfloor n\phi^2 \rfloor$, where $\phi = (1+\sqrt{5})/2$ (the golden section). Various generalizations and results on this game were done by Blass and Fraenkel \cite{Bla90}, Blass, Fraenkel, Guelman \cite{Bla98}, WW \cite{WW}, Coxeter \cite{Cox}, Dress \cite{Dre}, Fraenkel and Borosh \cite{Fra1973}, Fraenkel and Ozery \cite{Fra1998}, Fraenkel and Zusman \cite{Fra2001}, Landman \cite{Lan}, Yaglom and Yaglom \cite{Yag}. Another generalization of Wythoff's game, involving more than two piles, was proposed by Fraenkel \cite{Fra2003}, which is listed in the survey article by Guy and Nowakowski \cite{Guy} as one of the ``unsolved problems in combinatorial games". We are 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, for any non-zero vector of non-negative integers ($a_1$, $\dots$, $a_N$) whose {\it nim-sum} is $0$, remove $a_i$ tokens from the $i$-th pile (for $1 \leq i \leq N$). [Recall that the {\it nim-sum} (denoted by $\oplus$) is binary addition without carry. For example $3 \oplus 5$ equals $011 \oplus 101=110=6$.] Denote all the \PPoss{} by $$ (A^1, \dots, A^{N-2}, A^{N-1}_n, A^{N}_n), \quad , A^{N-2} \le A^{N-1}_n \le A^{N}_n $$ and $$ A^{N-1}_n < A^{N-1}_{n+1} \quad for \quad all \quad n \ge 0 \quad . $$ Fraenkel's conjectures are as follows. Fix $A^1, \dots, A^{N-2}$, then {\em Conjecture 1:} There exists an integer $N_1$ (depending only on $A^1, \dots, A^{N-2}$), such that when $n > N_1$, $A^{N}_{n} = A^{N-1}_{n} + n$. %\bigskip {\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 $\phi = (1+\sqrt{5})/2$ and $-1 \le \epsilon_n \le 1$. %\bigskip 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. In this paper, we prove the conjectures for the three-heap Wythoff's game when $A^1 \le \MaxResult$. \section{Preliminary Results} Throughout this paper, we use the notation $\phi = (1+\sqrt{5})/2$, the golden section. \begin{defn} 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$ 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} 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} \begin{lem} \label{lem_ws} Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$ and $N \ge n_0$ such that $A_n > \max(T)$ for all $n \ge N$, then \begin{enumerate} \item $1 \le A_{n+1} - A_n \le 2$, \item $2 \le B_{n+1} - B_n \le 3$, and \item if $A_{n} > B_N$, $A_{n+2} - A_n \ge 3$. \end{enumerate} \end{lem} Proof: By definition, $A_n - A_{n-1} \ge 1$, $B_n - B_{n-1} = A_n + n - A_{n-1} - (n-1) \ge 2$. Also, since $\{A_i\}_{i \ge n_0} \cup \{B_i\}_{i \ge n_0} = \mathbb{Z} - T$ and $A_n > \max(T)$, the only numbers between $A_n$ and $A_{n+1}$ are in $\{B_i\}_{i \ge n_0}$, which are not pair-wise sequential, therefore $A_{n+1} - A_n \le 2$ and $B_n - B_{n-1} = A_n - A_{n-1} + 1 \le 3$. Furthermore, if $A_{n+2} - A_n = 2$, let $B_m = \min\{B_i: B_i > A_{n+2}\}$, then $m > N$, $B_{m-1} < A_n$, so $B_m - B_{m-1} > 3$, which is contradictory to what we just proved. \begin{lem} \label{lem_gs} $\{(\lfloor n\phi \rfloor, \lfloor n\phi \rfloor + n)\}_{n \ge 1}$, the Wythoff's pairs as a sequence, is a special Wythoff's sequence. In addition to all the properties in Lemma~\ref{lem_ws}, it also satisfies the following: \begin{enumerate} \item $A = \{\lfloor n\phi \rfloor\}_{n \ge 1}$ and $B = \{n + \lfloor n\phi \rfloor\}_{n \ge 1}$ are complementary, i.e., $A \cup B = \mathbb{Z}_{>0}$ and $A \cap B = \emptyset$, \item $1 \le \lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor \le 2$, \item $|\lfloor n_1\phi \rfloor - \lfloor n_2\phi \rfloor - (n_1 - n_2)\phi| < 1$, \item if $\lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = 1$, then $\lfloor (n+1)\phi \rfloor - \lfloor n\phi \rfloor = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 2$, \item if $\lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 2$, then $\lfloor (n+1)\phi \rfloor - \lfloor n\phi \rfloor = \lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor = 1$. %\item $\phi(\phi - 1) = 1$. \end{enumerate} \end{lem} Proof: It is well explained by Fraenkel \cite{Fra1982} that the sequence satisfies all the requirements for special Wythoff's sequence. \begin{enumerate} \item See in \cite{Fra1982}. \item It is a direct corollary of the previous lemma. The first two items are highlighted again because they are of special interest to us in the coming sections. \item Since $\phi$ is irrational, $n_1\phi - 1 - n_2\phi < \lfloor n_1\phi \rfloor - \lfloor n_2\phi \rfloor < n_1\phi - n_2\phi + 1$. \item Since $\phi \approx 1.618$, for any $n$, $\lfloor n\phi \rfloor - \lfloor (n-2)\phi \rfloor > n\phi - 1 - (n-2)\phi > 2.2$. Since the left-hand side of the inequality is an integer, it is at least 3. \item Similarly for any $n$, $\lfloor n\phi \rfloor - \lfloor (n-3)\phi \rfloor < n\phi - (n-3)\phi + 1 < 5.9$. So the left-hand side can be at most 5. %\item $\phi$ is a root of $x^2 - x - 1 = 0$. \end{enumerate} \begin{lem} \label{lem_alphadiff} Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$ and $N \ge n_0$ such that $A_n > \max(T)$ for all $n \ge N$, if we write $A_n = \lfloor n\phi \rfloor + \alpha_n$ and $B_n = A_n + n + \alpha_n$, then $-1 \le \alpha_{n+1} - \alpha_n \le 1$ for all $n \ge N$. \end{lem} Proof: $\alpha_{n+1} - \alpha_{n} = (A_{n+1} - A_n) - (\lfloor (n+1)\phi \rfloor - \lfloor n\phi \rfloor)$, so the inequality holds because of Lemma~\ref{lem_ws} and Lemma~\ref{lem_gs}. \begin{lem} \label{lem_main} Given a Wythoff's sequence $\{(A_n, B_n)\}_{n \ge n_0}$, we assume that there exist integers $N$, $\alpha$, and $m_2 > m_1 > N + 2$, such that \begin{itemize} \item $A_n > \max(T)$, when $n > N$, \item $A_{m_2} > B_{m_1}$, \item $A_n = \lfloor n\phi \rfloor + \alpha + \epsilon_n$, where $m_1 - 2 \le n \le m_2$ and $-1 \le \epsilon_n \le 1$, and \item $\epsilon_{i-2}\epsilon_{i-1}\epsilon_{i} = 0$, when $m_1 - 2 \le i \le m_2$, \end{itemize} then $\epsilon_{i-1}\epsilon_{i} = 0$ for any $i > m_2$. \end{lem} Proof: The last assumption is equivalent to the statement that there do not exist three consecutive non-zero $\epsilon'$s by Lemma~\ref{lem_alphadiff} when $m_1 - 2 \le i \le m_2$, and we are to prove 1) $-1 \le \epsilon_{i} \le 1$ when $i > m_2$; and 2) there are no two consecutive non-zero $\epsilon'$s when $i > m_2$. Once proved, this lemma provides a way to evaluate the behavior of $\epsilon_n$, and {\em when} the behavior starts. We are going to prove the lemma in two steps: First, if $\exists n > m_2$ such that $\epsilon_n \notin \{0, \pm 1\}$, let $n$ be the smallest of such numbers, then $\epsilon_n = \pm 2$ by Lemma~\ref{lem_alphadiff}. There are four cases: a) $A_n = A_{n-1} + 2$ and $\epsilon_n = -2$: $\epsilon_{n-1} = -1$ by Lemma~\ref{lem_alphadiff}, and $A_{n} = \lfloor n\phi \rfloor + \alpha - 2 \le \lfloor (n-1)\phi \rfloor + \alpha$ by Lemma~\ref{lem_gs}. However, $A_{n} = A_{n-1} + 2 = \lfloor (n-1)\phi \rfloor + \alpha + 1$, which is impossible. b) $A_n = A_{n-1} + 2$ and $\epsilon_n = 2$: $\epsilon_{n-1} = 1$ by Lemma~\ref{lem_alphadiff}, so $\lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = A_n - A_{n-1} - (\epsilon_n - \epsilon_{n-1}) = 1$. By Lemma~\ref{lem_gs}, $\lfloor (n+1)\phi \rfloor - \lfloor n\phi \rfloor = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 2$. Since $A_n = A_{n-1} + 2$, there exists $m < n$ such that $B_m = A_n - 1 = A_{n-1} + 1$, i.e., $\lfloor m\phi \rfloor + m + \epsilon_m = \lfloor n\phi \rfloor + 1$. Since $\{\lfloor n\phi \rfloor + n\}$ and $\{\lfloor n\phi \rfloor\}$ are complementary and $\lfloor n\phi \rfloor = \lfloor (n+1)\phi \rfloor - 2$, we must have $\epsilon_m = 0$ and $\lfloor m\phi \rfloor + m = \lfloor n\phi \rfloor + 1$. Similarly since $\lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = 1$, $\lfloor (m-1)\phi \rfloor + m - 1 = \lfloor (n-1)\phi \rfloor - 1 = \lfloor m\phi \rfloor + m - 3$, thus $\lfloor m\phi \rfloor = \lfloor (m-1)\phi \rfloor + 2$. Also, since $2 \ge A_{n-1} - A_{n-2} = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor + \epsilon_{n-1} - \epsilon_{n-2} = 3 - \epsilon_{n-2}$, $\epsilon_{n-2}$ = 1 and $A_{n-1} - A_{n-2} = 2$. By our assumption of $\epsilon_{n-1}\epsilon_{n-2}\epsilon_{n-3} = 0$, we know $\epsilon_{n-3} = 0$, and by the definitions of $A_n$ and $B_n$, $B_{m-1} = A_{n-1} - 1$, which is to say $\lfloor (m-1)\phi \rfloor + m - 1 + \epsilon_{m-1} = \lfloor (n-1)\phi \rfloor$. Again, since $\{\lfloor n\phi \rfloor + n\}$ and $\{\lfloor n\phi \rfloor\}$ are complementary and $\lfloor n \phi \rfloor = \lfloor (n-1)\phi \rfloor + 1$, $\epsilon_{m-1}$ has to be 1. Now consider $A_{n-2} - A_{n-3}$, which is 1 or 2 by Lemma~\ref{lem_ws}. If $A_{n-2} - A_{n-3} = 1$, we have $1 = A_{n-2} - A_{n-3} = \lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor + 1 - \epsilon_{n-3}$, which means $\lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor = 1$ and $\epsilon_{n-3} = 1$. But then $\epsilon_{n-1}\epsilon_{n-2}\epsilon_{n-3} = 1$, which is contradictory to our assumption. If $A_{n-2} - A_{n-3} = 2$, $B_{m-2} = A_{n-2} - 1$, which means $\lfloor (m-2)\phi \rfloor + m - 2 + \epsilon_{m-2} = \lfloor (n-2)\phi \rfloor$. Again, since $\{\lfloor n\phi \rfloor + n\}$ and $\{\lfloor n\phi \rfloor\}$ are complementary and $\lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor = A_{n-2} - A_{n-3} - (\epsilon_{n-2} - \epsilon_{n-3}) = 1$, $\epsilon_{m-2}$ has to be $-1$. But $\epsilon_{m-1} = 1$, contradictory to Lemma~\ref{lem_alphadiff}. c) $A_n = A_{n-1} + 1$ and $\epsilon_n = 2$: By Lemma~\ref{lem_alphadiff}, $\epsilon_{n-1} = 1$, thus $\lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = A_n - A_{n-1} - \epsilon_n + \epsilon_{n-1} = 0$, which is impossible. d) $A_n = A_{n-1} + 1$ and $\epsilon_n = -2$: By Lemma~\ref{lem_ws}, $A_{n-1} = A_{n-2} + 2$, and by Lemma~\ref{lem_alphadiff}, $\epsilon_{n-1} = -1$. Therefore $-1 \le \epsilon_{n-2} = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor - 3$, so $\epsilon_{n-2} = -1$, $\lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 2$, and $\lfloor n \phi \rfloor - \lfloor (n-1)\phi \rfloor = A_{n} - A_{n-1} - (\epsilon_{n} - \epsilon_{n-1}) = 2$ thus $\lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor = 1$ by Lemma~\ref{lem_gs}. However $1 \le A_{n-2} - A_{n-3} = \lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor - 1 - \epsilon_{n-3}$, which means $\epsilon_{n-3} = -1$ and $\epsilon_{n-1}\epsilon_{n-2}\epsilon_{n-3} = -1$, contradictory to our assumption. Secondly, if there exists $n > m_2$ such that $\epsilon_n \epsilon_{n-1} \ne 0$, i.e., $\epsilon_n = \epsilon_{n-1} = \pm 1$, let $n$ be the smallest of such numbers, then by Lemma~\ref{lem_ws} and by what we have just proved, $\epsilon_{n-2} = 0$. There are two cases: e) $\epsilon_n = \epsilon_{n-1} = 1$: $2 \ge A_{n-1} - A_{n-2} = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor + 1$, so $\lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 1$ and $A_{n-1} - A_{n-2} = 2$. Also $A_{n} - A_{n-1} = \lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = 2$ by Lemma~\ref{lem_gs}. So there exists $m < n $ such that $B_m = A_{n} - 1$ and $B_{m-1} = A_{n-1} - 1$, which means $\lfloor m\phi \rfloor + m + \epsilon_m = \lfloor n\phi \rfloor$ and $\epsilon_m = \pm 1$; $\lfloor (m-1)\phi \rfloor + m - 1 + \epsilon_{m-1} = \lfloor (n-1)\phi \rfloor$ and $\epsilon_{m-1} = \pm 1$. Since $\{\lfloor n\phi \rfloor + n\}$ and $\{\lfloor n\phi \rfloor\}$ are complementary and $\lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 1$, $\epsilon_{m-1} = -1$, therefore $\epsilon_{m} = \epsilon_{m-1} = -1$ by Lemma~\ref{lem_alphadiff}, and $\lfloor m\phi \rfloor + m = \lfloor n\phi \rfloor + 1$. So $\lfloor (n+1)\phi \rfloor = \lfloor n\phi \rfloor + 2$, and $\lfloor (n+2)\phi \rfloor = \lfloor (n+1)\phi \rfloor + 1$ by Lemma~\ref{lem_gs}. Thus $\lfloor (m+1)\phi \rfloor + m + 1 = \lfloor (n+2)\phi \rfloor + 1 = \lfloor m\phi \rfloor + m + 3$, and $3 \ge B_{m+1} - B_m = \lfloor (m+1)\phi \rfloor + m + 1 + \epsilon_{m+1} - (\lfloor m\phi \rfloor + m - 1) = 4 + \epsilon_{m+1}$. Therefore $\epsilon_{m+1} = -1$ and $\epsilon_{m+1}\epsilon_{m}\epsilon_{m-1} = -1$, contradictory to our assumption. f) $\epsilon_n = \epsilon_{n-1} = -1$: $1 \le A_{n-1} - A_{n-2} = \lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor - 1$, so $\lfloor (n-1)\phi \rfloor - \lfloor (n-2)\phi \rfloor = 2$ and $A_{n-1} - A_{n-2} = 1$. Thus $A_{n} - A_{n-1} = A_{n-2} - A_{n-3} = 2$ by Lemma~\ref{lem_ws}, and $\lfloor n\phi \rfloor - \lfloor (n-1)\phi \rfloor = A_{n} - A_{n-1} = 2$. Hence $\lfloor (n+1)\phi \rfloor - \lfloor n \phi \rfloor = \lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor = 1$ by Lemma \ref{lem_gs}. Therefore there exists $m < n$ such that $B_m = A_{n} - 1$, $B_{m-1} = A_{n-2} - 1$, that is $\lfloor n\phi \rfloor - 2 = \lfloor m\phi \rfloor + m + \epsilon_m$, and $\lfloor (m-1)\phi \rfloor + m - 1 + \epsilon_{m-1} = \lfloor (n-2)\phi \rfloor - 1$. Since $\{\lfloor n\phi \rfloor + n\}$ and $\{\lfloor n\phi \rfloor\}$ are complementary and $\lfloor n\phi \rfloor = \lfloor (n-1)\phi \rfloor + 2$, $\epsilon_{m} = \pm 1$. Similarly, since $\lfloor (n-2)\phi \rfloor - \lfloor (n-3)\phi \rfloor = 1$, $\epsilon_{m-1} = 1$, which means $\epsilon_{m} = \epsilon_{m-1} = 1$ by Lemma~\ref{lem_alphadiff}. So $\lfloor m\phi \rfloor + m = B_{m} - 1 = A_n - 2 = \lfloor n\phi \rfloor - 3$, and $\lfloor (m+1)\phi \rfloor + m + 1 = \lfloor n\phi \rfloor - 1$, thus $\lfloor (m+1)\phi \rfloor = \lfloor m\phi \rfloor + 1$. Since $2 \le B_{m+1} - B_{m} = 1 + \epsilon_{m+1}$, $\epsilon_{m+1} = 1$ and $\epsilon_{m+1}\epsilon_{m}\epsilon_{m-1} = 1$, contradictory to our assumption. \section{Main Results} In this section, we adopt the following notation: \begin{itemize} \item $[a, b, c]$, $a \ge 0$, $b \ge 0$, $c \ge 0$, is a three-heap Wythoff's position having $a$, $a + b$ and $a + b + c$ tokens in the piles; \item $[m, A^m_n, B^m_n]$, where $n \ge 1$ and $A^m_n < A^m_{n+1}$, are all the \PPoss{} whose first piles have $m$ tokens; \item $P^{m}$ is the set of \PPoss{} whose first piles have $m$ tokens; \item $T^m = \mathbb{Z}_{\ge 0} - \{A^m_i, A^m_i + B^m_i: i \ge 1\} - \{i: 0 \le i < m\}$; \item $S^m = \mathbb{Z}_{\ge 0} - \{B^m_i: i \ge 1\}$; \item $\alpha_n^m = m + A^m_n - \lfloor B^m_n \phi \rfloor$; \item $N_1^m$ is the integer such that when $n > N_1^m$, $A_n^m = mex\{A^m_i, B^m_i: 1 \le i < n\}$ and $B^m_{n+1} = B^m_{n} + 1$; \item $N_2^m$, $\alpha^m$, and $\epsilon^m_n$ are the integers such that when $n > N_2^m$; $A_n^m = mex\{A^m_i, B^m_i: 1 \le i < n\}$, $B^m_{n+1} = B^m_{n} + 1$; and $\epsilon^m_n = m + A^m_{n} - \lfloor B^m_{n}\phi \rfloor - \alpha^m \in \{0, \pm 1\}$; \item $N_3^m$ is the integer such that if $N_2^m$ exists and when $n > N_3^m$, $\epsilon^m_n \epsilon^m_{n+1} = 0$; \item $\nimp(m) = 2^{\lfloor \log_{2}(m) \rfloor + 1}$. \end{itemize} With the notation above, each list of three numbers {\em uniquely} identifies a three-heap position, and vice versa. For our convenience and without any confusion, we also use $[0, b, c]$ to denote two-heap positions. We will also 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 obtain a Wythoff's sequence by chopping off a number of pairs from the sequence and reorganizing the indices. The conjectures can now be rephrased as follows. For any given $m \ge 0$, $[A^m_n, A^m_n + B^m_n]$ is a special Wythoff's sequence. In other words, $N_1^m$, $N_2^m$ and $\alpha^m$ exist. \begin{clm} $T^m = \{ b : \exists a < m,\ such\ that\ [a, m - a, b] \in P^{a}\}$, thus it is finite. \end{clm} Proof: Denote the right-hand side of the equation as $T_1$. If $b \in T_1$, $[m, b, c]$, is an \NPos{} for any $c \ge 0$, because we can simply remove an appropriate number of tokens from the third pile to create a \PPos. Similarly, $[m, c, b - c]$ is also an \NPos{} for any $c \le b$, because we can remove tokens from the second pile. Hence $T_1 \subset T^m$. On the other hand, if $b \in T^m$, $[m, b, c]$ is an \NPos{} for any $c \ge 0$. By the rules, to find the \PPos{} corresponding to $[m, b, c]$ for each $c$, we can I) remove $b_1$, $b_2$, $b_3$ tokens from the three piles correspondingly, providing $b_1 \oplus b_2 \oplus b_3 = 0$ and $b_1 + b_2 + b_3 > 0$; %\smallskip II) remove $a_1$ tokens from the first pile where $0 < a_1 \le m$; %\smallskip III) remove $b_1$ tokens from the second pile where $0 < b_1 \le b + m$; %\smallskip IV) remove $c_1$ tokens from the third pile where $0 < c_1 \le m + b + c$. %\bigskip There are only finitely many choices involving moves I), II) and III), but infinitely many choices of $c$, so there must exist $0 \le c' < b + m$, such that a \PPos{} has $m$, $c'$ and $b + m$ tokens in the piles. Since $b \in T^m$, $c' < m$. Thus $b \in T_1$ and $T^m \subset T_1$. %\bigskip It is easy to see that $T^1 = \{1\}$ because of $[0, 1, 1]$; $T^2 = \emptyset$; and $T^3 = \{1, 2, 3\}$ because of $[1, 2, 1]$, $[0, 3, 2]$ and $[2, 1, 3]$. We implement the following steps in order to prove the conjectures on the Wythoff's game for any specific $m$. \begin{clm} \label{clm_1} We can represent positions in the three-heap Wythoff's game symbolically, and therefore can create a generating function to find \PPoss. \end{clm} Proof: Given a \PPos{} $[a, b, c]$, $a \le m$, the following positions whose first piles have $m$ tokens can reach this position with one move: \begin{equation} [m, b + b' - (m - a), c + ((m - a) \oplus b') - b'],\ b' \ge 0, \ if\ a < m \label{wgm_1} \end{equation} \begin{equation} [m, a + a' - m, b + c + ((m - a - b) \oplus a') - a'],\ a' \ge m - a, \ if\ a + b < m \label{wgm_2} \end{equation} \begin{equation} [m, a + a' - m, b + ((m - a - b - c) \oplus a') - a'],\ a' \ge m - a, \ if\ a + b + c < m \label{wgm_3} \end{equation} \begin{equation} [m, b + b', c - b'],\ b' \le c, \ if\ a = m \label{wgm_4} \end{equation} \begin{equation} [m, b + c, b'],\ b' \ge 0, \ if\ a = m \label{wgm_5} \end{equation} \begin{equation} [m, b, c + c'],\ c' \ge 0, \ if\ a = m \label{wgm_6} \end{equation} \begin{equation} [m, b', c - b'],\ 0 \le b' \le c, \ if\ a + b = m \label{wgm_7} \end{equation} \begin{equation} [m, c, c'],\ c' \ge 0, \ if\ a + b = m \label{wgm_8} \end{equation} \begin{equation} [m, b', b + c],\ b' \ge 0, \ if\ a + b = m \label{wgm_9} \end{equation} \begin{equation} [m, b', b],\ b' \ge 0, \ if\ a + b + c = m \label{wgm_10} \end{equation} %\begin{eqnarray} % [m, b + b' - (m - a), c + ((m - a) \oplus b') - b'],\ b' \ge 0, % & if\ a < m \label{wgm_1} \\ % [m, a + a' - m, b + c + ((m - a - b) \oplus a') - a'],\ a' \ge m - a, % & if\ a + b < m \label{wgm_2} \\ % [m, a + a' - m, b + ((m - a' - b - c) \oplus a') - a],\ a' \ge m - a, % & if\ a + b + c < m \label{wgm_3} \\ % [m, b + b', c - b'],\ b' \le c % & if\ a = m \label{wgm_4} \\ % [m, b + c, b'],\ b' \ge 0 % & if\ a = m \label{wgm_5} \\ % [m, b, c + c'],\ c' \ge 0 % & if\ a = m \label{wgm_6} \\ % [m, b', c - b'],\ 0 \le b' \le c % & if\ a + b = m \label{wgm_7} \\ % [m, c, c'],\ c' \ge 0 % & if\ a + b = m \label{wgm_8} \\ % [m, b', b + c],\ b' \ge 0 % & if\ a + b = m \label{wgm_9} \\ % [m, b', b],\ b' \ge 0 % & if\ a + b + c = m \label{wgm_10} %\end{eqnarray} The ten sets of positions above correspond to the following moves. Add tokens to the original position to: %\begin{tabular}{l} \begin{itemize} \item all three rows, with $m-a$ tokens to the first pile, $b'$ second and $(m-a) \oplus b'$ third, \item all three rows, with $a'$ first, $m-a-b$ second and $(m-a-b) \oplus a'$ third, \item all three rows, with $a'$ first, $(m-a-b-c) \oplus a'$ second and $m-a-b-c$ third, \item the second row, but not enough to exceed the third, \item the second row, and exceeding the third, \item the third row only, \item the first row, but not enough to exceed the third, \item the first row, and exceeding the third, \item the first and the third rows, \item the first and second rows, and both exceeding the third. \end{itemize} %\end{tabular} Also in cases of \ref{wgm_1}, \ref{wgm_2} and \ref{wgm_3}, we may need to increase the second and third numbers to avoid possible negative values: if $[m, b', c']$ is the resulting \NPos{} and $c' < 0$, we will change it to $[m, b'+ c', -c']$; and if $b'$ or $b' + c'$ is less than 0, we simply replace it with 0. Therefore, if $[a, b, c]$ is a \PPos, the positions listed above are all the \NPos{} deduced from it. So for each position $(A^1, A^{2}_n, A^{3}_n)$ in the game, $N$ or $P$, by fixing the first pile, we can use $x_1^{A^{2}_n} x_2^{A^{3}_n}$ to represent it symbolically. By observing that for any given $b$, $(b \oplus c) - c$ is periodic as a function of $c$ with period $\nimp(b)$. we know that for each \PPos{} $[a, b, c]$, all the \NPoss\ deduced from it, possibly including $[a, b, c]$ itself, are: %\begin{eqnarray} \begin{equation} \sum_{k=0}^{\nimp(m-a) - 1} \frac{x_1^b x_2^c}{ 1-x_2^{((m - a) \oplus k) - k}}, \ if\ a < m \label{eq_1} \end{equation} \begin{equation} \sum_{k=0}^{\nimp(m-a-b) - 1} \frac{x_2^{b+c}}{ 1-x_2^{((m-a-b) \oplus (m-a+k)) - (m-a+k)}}, \ if\ a < m \label{eq_2} \end{equation} \begin{equation} \sum_{k=0}^{\nimp(m-a-b-c) - 1} \frac{x_2^{b+c}}{ 1-x_2^{((m-a-b-c) \oplus (m-a+k)) - (m-a+k)}}, \ if\ a < m \label{eq_3} \end{equation} \begin{equation} \sum_{k=0}^{c}(x_1^{b+k} x_2^{c-k}), \ if\ a = m \label{eq_4} \end{equation} \begin{equation} \frac{x_1^{b+c}}{1-x_2}, \ if\ a = m \label{eq_5} \end{equation} \begin{equation} \frac{x_1^{b} x_2^{c}}{1-x_2}, \ if\ a = m \label{eq_6} \end{equation} \begin{equation} \sum_{k=0}^{c}(x_1^{k} x_2^{c-k}), \ if\ a + b = m \label{eq_7} \end{equation} \begin{equation} \frac{x_1^{c}}{1-x_2}, \ if\ a + b = m \label{eq_8} \end{equation} \begin{equation} \frac{x_2^{b+c}}{1-x_1}, \ if\ a + b = m \label{eq_9} \end{equation} \begin{equation} \frac{x_2^{b}}{1-x_1}, \ if\ a + b + c = m \label{eq_10} \end{equation} %\end{eqnarray} Given a position $[a, b, c]$, let $N([a, b, c])$ be the set of all positions that can reach $[a, b, c]$ with one move, and denote by $f([a, b, c])$ the sum of the formal series \ref{eq_1}--\ref{eq_10}, whenever applicable. Then $f$ is the sum of the symbolic representations of $[a, b, c]$ and $N([a, b, c])$. We now define: \begin{displaymath} F_1(x_1, x_2) = \sum_{[a, b, c] \in P^{a},\ all\ a < m} f([a, b, c]) \quad, \end{displaymath} \begin{displaymath} F_2(x_1, x_2) = \sum_{[a, b, c] \in P^{m}} f([a, b, c]) \quad , \quad and \end{displaymath} \begin{displaymath} F(x_1, x_2) = \frac{1}{(1-x_1)(1-x_2)} - F_1(x_1, x_2) - F_2(x_1, x_2) \quad . \end{displaymath} The sum for $F_2(x_1, x_2)$ is over the set of all known \PPoss{} in $P^{m}$; and the sum for $F_1(x_1, x_2)$ is over the set of all \PPoss{} whose first pile have less than $m$ tokens with $b$ and $c$ large enough. We consider the Taylor expansion of $F(x_1, x_2)$ and find the lexicographically first monomial with strictly positive coefficient. The next \PPos{} will be $[m, b, c]$, which always exists based on the rules of the game. In practice, we will use a faster approach to find $A_n^m$, namely $A^m_n = mex\{A^m_i, A^m_i + B^m_i : 0 \le i < n\}$, and still use the generating function to find $B^m_i$. The reason that we can use {\it mex} here is because of our assumption $A^m_{n-1} < A^m_{n}$, which indicates that any integer between the two must be in $\{A^m_i + B^m_i\}_{0 \le i < n} \cup T$. The game can also be visualized as follows. When the first pile has a fixed amount, $m$, of tokens, consider all the positions as points in the first quadrant with integral coordinates. For example, a position $[m, b, c]$ will be represented by the point $(b, c)$ in our coordinate system. We call {\em instant winners} the positions at which a player can declare himself a winner immediately. In our game, they are the positions $[m, b, c]$ such that they can reach a certain $[a', b', c'] \in P^{a}$ with $a' < m$. Cross these points out of our coordinate system, and find the first point $[b, c]$ that has not been erased with the smallest possible $x$, and for that $x$, the smallest $y$ coordinate. By the rules of the game, $[m, b, c]$ is a \PPos. After finding each \PPos $[m, b, c]$, we draw the following lines starting from $(b, c)$: an upward vertical line, a leftward horizontal line, a $45^\circ$ south-eastern slant line and an upward vertical line starting from the $x$-intercept of the slant line. Remove all the points on the lines, because they are the \NPoss{} that can reach the newly found \PPos{} with one move. Repeat the process to find the next \PPos. In Figure \ref{fig_1}, $m = 1$; each (small) cross is an instant winner; and each ``X" is a \PPos. \begin{center} \begin{figure}[!ht] \includegraphics[width=5in, height=4in]{wyt_1} %\includegraphics[width=0.5\textwidth, scale=1]{wyt_1} \caption{\PPoss{} and instant winners when $m = 1$ and $n \le 28$} \label{fig_1} \end{figure} \end{center} \begin{clm} \label{clm_4} Given all $[m, A^m_i, B^m_i] \in P^{m}$, with $i \le N$, We can decide whether a given integer $c < B^m_N$ is in $S^m$ by the following rules. \begin{itemize} \item if there exists $[a, b, c] \in P^{a}$ and $a + b = m$, then $b + c \in S^m$; \item if there exists $[a, b, c] \in P^{a}$ and $a + b + c = m$, then $b \in S^m$; \item if there exists $n$ such that $B_i \neq c$ when $i < n$; $B_n > c$; and coeff$(F_{2,n}(x_1), x_1, i) \le 0$ with $A_n \le i \le A_n + \nimp(m)$, then $c \in S^m$. \end{itemize} \end{clm} Proof: Here we can see the advantage of symbolic over numeric computing, even though the latter would have been faster if we were {\it only} looking for the next \PPoss. Consider the generating function $F_1(x_1, x_2)$ generated by all the \PPoss, whose first piles have less than $m$ pieces, and their induced \NPoss, namely, the sum of the formal power series \ref{eq_1}, \ref{eq_2}, \ref{eq_3}, \ref{eq_7}, \ref{eq_8}, \ref{eq_9} and \ref{eq_10} over all the \PPoss{} described above. Let $F_{1,n}(x_1, x_2)$ be the Taylor expansion of $F_1(x_1, x_2)$ of degree $\max\{A^m_i + B^m_i : i \le n \} + \nimp(m)$. Denote coeff$(f(x), x, n)$ as the coefficient of $x^{n}$ of the Taylor expansion of $f(x)$, and let $F_{2,n}(x_1)$ be coeff$(F_{1,n}(x_1, x_2), x_2, c)$. So from the proof of the previous claim, $c \in S^m$ if we can show that there exists $N$ such that $B^m_n \neq c$ when $A^m_n \le N$, and coeff$(F_{2,n}(x_1), n)$ are all positive when $n > N$. The first two cases are obvious because we can remove the same number of tokens from two different piles, or symbolically we can use \ref{eq_9} and \ref{eq_10}, and work with the coefficients of the corresponding formal series. In the third case, we only consider the moves that remove tokens from all three piles, or equivalently, cases \ref{wgm_1}, \ref{wgm_2} and \ref{wgm_3}, which generate formal series \ref{eq_1}, \ref{eq_2} and \ref{eq_3}. By our notation, each monomial $x_1^a x_2^b$ with positive coefficient in the Taylor expansions of the fractional expressions represents either the \PPos{} that generates the terms or an \NPos{} $[m, a, b]$ deduced from the \PPos. By the previously mentioned fact that $(a \oplus b) - b$ is periodic as a function of $b$, with period $\nimp(a)$, which divides $\nimp(m)$ if $a \le m$. Therefore if such an $n$ exists as described above, coeff$(F_{2,n}(x_1), x_1, i) \ge 0$ for any $i \ge A_n$, and this finishes the proof of our claim. We denote all such numbers as $S_1^m(n)$, which is a subset of $S^m$. For example when $m = 1$, $2 \in S^1$ because $[0, 1, 1] \in P^{0}$; $17 \in S^1$ because $[1, 24, 18] \in P^{1}$ and checking the generating function at that point confirms the result. In fact, manual check indicates that when $n < 29$, there is no \PPos{} of the form $[1, n, 17]$; when $n \ge 15$, $[1, 2n-1, 17]$ are all \NPoss{} because $[0, 29, 18] \in P^{0}$, and $[1, 2n, 17]$ are all \NPoss{} because $[0, 25, 16] \in P^{0}$. Such manual checks become impractical as $m$ grows larger. Interested readers can try to check another simple one: $22 \in S^1$. In the language of instant winners, $c \in S_1^m(n)$ means the instant winners will fill the horizontal line $y = c$ for $x > A^m_n$, e.g. check $c = 2, 17$ in Figure \ref{fig_1}. \begin{clm} \label{clm_5} There exists an integer $N$ such that when $n > N$, $A^m_n > \max\{T^i: i \le m\}$ and $B^m_n > m + \max\{T^i: i \le m\}$. If for a given $n > N$, $B = \max(\{B^m_i: i \le n\})$, $mex(\{B^m_i: i \le n\} \cup S_1^m(n)) = B + 1$, and $B + 1 - B_{n'}^{i} > m - a$ whenever $i + A_{n'}^{i} \le m + A^m_{n+1}$ with $0 \le i < m$, then $B^m_{n+1} = B + 1$. \end{clm} Proof: Since $T^i$, $i < m$, are all finite, there must exist an integer $N$ as specified. If there is an $n > N$ as described in the assumption, let us consider the position $[m, A^m_{n+1}, B + 1]$. To prove it is a \PPos{}, we only need to show that it cannot reach another \PPos{} with one move. For any $[a, b, c] \in P^{a}$ with $a < m$ and $a + b \le m + A^m_{n+1}$, the moves like \ref{wgm_7}, \ref{wgm_8}, \ref{wgm_9} and \ref{wgm_10} require $b \le m$ and $c \in T^i$ for some $i < m$, so the moves can change the second number to at most $\max\{T^i: i \le m\}$ or the third number to $m + \max\{T^i: i \le m\}$. So these moves cannot affect $[m, A^m_{n+1}, B + 1]$ being a \PPos{} or \NPos. Since $B + 1 - c > m - a$ and $(a_1 \oplus a_2) - a_2 \le a_1$ for any $a_1$ and $a_2$, when the moves like \ref{wgm_1}, \ref{wgm_2}, \ref{wgm_3} change the first and second numbers of $[a, b, c]$ to $m$ and $A^m_{n+1}$, they can change the third number from $c$ to at most $m - a + c$, i.e., the third pile has at most $m + A^m_{n+1} + m + c - a < m + A^m_{n+1} + B + 1$ tokens, which means these moves are all irrelevant too. Thus we have been freed from the possible moves that involve the first pile. On the other hand, all the moves that involve only the second and third piles, namely \ref{wgm_4}, \ref{wgm_5} and \ref{wgm_6}, will not increase both of the second and the third numbers at the same time, so $B^m_{n+1} = mex(\{B^m_i: i \le n\} \cup S^m) = B + 1$. Using the visual interpretation of game, we can view the result as: $B^m_{n+1} = mex(\{B^m_i: i \le n\} \cup S^m) + 1$, if the instant winners are not involved in the decision-making. For example, check the \PPoss{} when $c \ge 23$ in Figure \ref{fig_1}. This claim provides us a sufficient condition to verify {\em when} $B^m_{n+1} = B^m_{n} + 1$. \begin{clm} \label{clm_5.5} For a given $m$, if $N^i_1$, $N^i_2$ and $N^i_3$ exist for $i < m$, the following conditions imply both conjectures for $m$: given an integer $N$ as in Claim \ref{clm_5}, if there exist $n_1 > n_2 > N$ such that \begin{itemize} \item $A^m_{n_2 + 3} + B^m_{n_2 + 3} < A^m_{n_1}$; \item $B_{j+1}^m = B_j^m + 1$ for $n_2 \le j \le n_1$; \item $B^m_{n_1} = \max(\{B^m_{i}: i \le n_1\}$; \item $mex(\{B^m_{i}: i \le n_1\} \cup S_1^m(n_1)) = B^m_{n_1} + 1$; \item $\max(\alpha_{j}^m: n_2 \le j \le n_1) - \min(\alpha_{j}^m: n_2 \le j \le n_1) \le 2$; \item $B_{n_1}^m > B^i_{N^i_3}$, $i < m$; \end{itemize} Furthermore if we denote $\alpha' = \lfloor (\max(\alpha^m: n_2 \le j \le n_1) - \min(\alpha^m: n_2 \le j \le n_1)) / 2 \rfloor$ and $\epsilon_i^m = m + A^m_i - \lfloor B^m_i \phi \rfloor - \alpha'$, $i \ge 1$, we also assume: \begin{itemize} \item $\alpha^i - \alpha' \ge 4(m - i)$, $0 \le i < m$; \item $\epsilon_{j}^m\epsilon_{j-1}^m\epsilon_{j-2}^m = 0$, $n_2 < j < n_1$. \end{itemize} \end{clm} Proof: Note that although there are eight conditions in the assumption, the first six are in fact necessary conditions for the conjectures. We prove this Claim by induction and assume all the conditions are true for $n \ge n_1$, i.e., $mex(\{B^m_{i}: i \le n\} \cup S_1^m(n)) = B^m_{n} + 1$, $B_{n}^m = B_{n-1}^m + 1$, and $|\epsilon_n| \le 1$. To prove $B^m_{n+1} = B^m_{n} + 1$, by Claim \ref{clm_5}, we need to show that if $i + A_{n'}^i \le m + A_{n+1}^m$ with $i < m$, then $B_n^m + 1 > B^i_{n'} + m - i$. Since $A_{n+1}^m \le A_{n}^m + 2$, $\lfloor B^m_n \phi \rfloor + \alpha' + \epsilon^m_n + 2 - \lfloor B^i_{n'} \phi \rfloor - \alpha^i - \epsilon^i_{n'} \ge 0$, therefore $\lfloor B^m_n \phi \rfloor - \lfloor B^i_{n'} \phi \rfloor \ge \alpha^i - \alpha' - 4$; $(B^m_n - B^i_{n'}) \phi + 1 > \alpha^i - \alpha' - 4$; $B^m_n + 1 - B^i_{n'} > (\alpha^i - \alpha' - 5) / \phi + 1$; so $B^m_n + 1 - B^i_{n'} \ge m - i$. The only time that the equal sign may hold is when $m = i + 1$, $\alpha^i - \alpha' = 4$, $\epsilon^i_{n'} = -1$, $\epsilon^m_n = 1$, and $B^m_n = B^i_{n'} = B$. By Lemma~\ref{lem_main} and the assumption $B^i_{n'} = B_{n}^m > B^i_{N^i_3}$, $\epsilon^i_{n'-1} = \epsilon^m_{n-1} = 0$. Thus $A_{n}^m - A_{n-1}^m = \lfloor B \phi \rfloor - \lfloor (B - 1) \phi \rfloor + 1$ and $A_{n'}^i - A_{n'-1}^i = \lfloor B \phi \rfloor - \lfloor (B - 1) \phi \rfloor - 1$. If $\lfloor B \phi \rfloor - \lfloor (B - 1) \phi \rfloor = 1$, $A_{n'}^i - A_{n'-1}^i = 0$; and if $\lfloor B \phi \rfloor - \lfloor (B - 1) \phi \rfloor = 2$, $A_{n}^m - A_{n-1}^m = 3$. Neither of the two cases is possible. So $B^m_{n+1} = B^m_{n} + 1$ and % $A^m_{n+1} = \lfloor B^m_{n+1} \phi \rfloor + \alpha' + \epsilon_{n+1}$, $|\epsilon^m_{n+1}| \le 1$ by Lemma~\ref{lem_main}. It is also obvious now that $S_1^m(n) = S_1^m(n+1)$, $B^m_{n+1} = \max(\{B^m_{i}: i \le n + 1\}$ and $mex(\{B^m_{i}: i \le n+1\} \cup S_1^m(n+1)) = B^m_{n+1}+1$, therefore we have completed the induction. In this case, $\alpha^m = \alpha'$ and $S^m = S^m_1(n_1)$. \begin{clm} \label{clm_6} When $m < \MaxResult$, $\{(A^m_n, A^m_n + B^m_n)\}_{n \ge 0}$ are special Wythoff's sequences, and thus we have proved the conjectures. \end{clm} Proof: By using Claim~\ref{clm_5.5}, we only need to show that the two integers $n_1$ and $n_2$ do exist. Table~\ref{tbl:main} lists results for $m \le \MaxResult$, in which we still use the same notations $T^m$, $S^m$, $\alpha^m$, $N_1^m$ and $N_2^m$ as described at the beginning of the section. Complete results and the associated Maple package are available at \newline {\em http://math.temple.edu/$\sim$xysun/wythoff/wythoff.htm}. As we can see, the results for $m = 1$ are consistent with the ones predicted by Fraenkel \cite{Fra2003}, that also appear in Guy, R. J. Nowakowski \cite{Guy}, since the 21st and 28th \PPoss{} are $[1, 32, 23]$ and $[1, 44, 30]$ respectively. (Note that our notation differs slightly from that of \cite{Fra2003}, so some of the signs are reversed). \begin{center} \begin{table} \begin{tabular} {|r|r|r|r|r|r|r|} \hline \em m & \em $T^m$ & \em $S^m$ & $\alpha^m$ & $N_1^m$ & $N_2^m$ \\ \hline 0 & & & 0 & 1 & 1 \\ [2mm] 1 & 1 & 2, 17, 22 & -4 & 21 & 28 \\ [2mm] 2 & & 1, 5, 8, 24, 26, 32 & -10 & 28 & 58 \\ [2mm] 3 & 1, 2, 3 & 2, 3, 4, 5, 8, 10, 11, 12, 28, 41, 57 & -16 & 48 & 73 \\ [2mm] 4 & 3, 6 & 2, 5, 6, 7, 8, 9, 11, 12, 14, 17, 46, 48, 59 & -20 & 126 & 208 \\ [2mm] 5 & 4, 7, 10 & 1, 3, 5, 6, 8, 10, 11, 12, 15, 16, 17, 18, 19, & -26 & 71 & 123 \\ & & 28, 56, 77, 83 & & & \\ [2mm] 6 & 2, 3, 4, 6 & 1, 2, 3, 4, 5, 7, 8, 10, 11, 12, 13, 14, 15, & -32 & 113 & 232 \\ & & 16, 18, 21, 44, 58, 95, 96, 132 & & & \\ [2mm] 7 & 1, 4, 6, 7, 9 & 0, 1, 2, 4, 5, 6, 7, 8, 10, 12, 13, 14, 15, 17, 18, & -39 & 227 & 343 \\ & & 19, 21, 22, 23, 24, 28, 30, 86, 88, 232, 251 & & & \\ [2mm] 8 & 3, 5, 10, 13 & 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 16, 17, 19, & -46 & 388 & 648 \\ & & 20, 21, 22, 24, 26, 27, 28, 33, 34, 46, 155, 257, & & & \\ & & 390, 415 & & & \\ [2mm] 9 & 6, 4, 11, 15 & 0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, & -52 & 645 & 645 \\ & & 16, 18, 19, 20, 24, 25, 26, 27, 30, 36, 37, 44, & & & \\ & & 48, 62, 254, 388, 421, 676 & & & \\ [2mm] 10 & 6, 7, 8, 9, 13 & 0, 1, 2, 3, 5, 6, 7, 9, 10, 11, 12, 13, 14, 15, & -56 & 656 & 656 \\ & & 16, 17, 18, 19, 20, 21, 22, 25, 27, 28, 29, 30, & & & \\ & & 31, 32, 34, 39, 50, 53, 103, 391, 424, 690 & & & \\ \hline \end{tabular} \vspace{5mm} \caption{Results on Three-Heap Wythoff's Games} \label{tbl:main} \end{table} \end{center} \section{Epilogue} The method discussed here should be able to be extended to prove the conjectures for Wythoff's games with more than three heaps. A numerical method, instead of the symbolic one presented here, may also be developed to improve the performance, provided Claim~\ref{clm_4} can be proved without using the generating functions. We hope the result presented here would be a stepping-stone for others to finally prove the conjectures, and better yet, to provide a {\it constructive} polynomial-time winning strategy for the game. \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{Bla98} U. Blass, A. S. Fraenkel and R. Guelman, How far can Nim in disguise be stretched?, {\em J. Combin. Theory.} (Ser. A) \textbf{84} (1998) 145--156. \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{Cox} H. S. M. Coxeter, The golden section, phyllotaxis and Wythoff's game, {\em Scripta Math.} \textbf{19} (1953) 135--143. \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{Fra1982} A. S. Fraenkel, How to beat your Wythoff games' opponent on three fronts, {\em Amer. Math. Monthly} \textbf{89} (1982) 353--361. \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{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{Fra1998} A. S. Fraenkel and M. Ozery, Adjoining to Wythoff's game its P-Positions as moves, {\em Theoret. Comput. Sci.} \textbf{205} (1998) 283--296. \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{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{Wyt} W. A. Wythoff, A modification of the game of Nim, {\em Nieuw Arch. Wisk.} \textbf{7} (1907) 199--202. \bibitem{Yag} A. M. Yaglom and I. M. Yaglom, {\em Challenging mathematical problems with elementary solutions}, Vol.II, Holden-Day, San Francisco, translated by J. McCawley, Jr., revised and edited by B. Gordon, 1967. \end{thebibliography} \end{document}