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


%\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}

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

\numberwithin{equation}{section}

\begin{document}

\title{The Sprague-Grundy Function for Chomp }

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




\begin{abstract}
When the top rows of Chomp positions are fixed to certain values, 
the differences of the number of squares in the first rows and the values of 
the Sprague-Grundy function are periodic. The article also found a complete
formula for the Sprague-Grundy function for the two-rowed Chomp positions.
\end{abstract}


\maketitle


\section{ Introduction }

Chomp \cite{CH} is a two-player game that starts out with an $M$ by $N$ chocolate bar, in which 
the square on the top-left corner is poisonous. A player must name a remaining square, and eat 
it together with all the squares below and/or to the right of it. Whomever eats the 
poisonous one (top-left) loses. The game can also be interpreted as two players 
alternately naming a devisor of a given number $N$, which may not be multiples of 
previously named numbers. Whomever names 1 loses. 

Of course Chomp is an impartial game, therefore each position has its own 
nim value by the Sprague-Grundy theorem [Sprague 1935-1936; Grundy 1939] 
which states that every position in an impartial game 
is equivalent to a Nim heap. The nim values are often referred as the values
of the {\em Sprague-Grundy (or Grundy) function}, and the $\mathcal{P}$-positions
are the ones whose value of the Grundy function are 0. 
Basic facts on the theory of combinatorial games and the Sprague-Grundy function
can be found in \cite{CG}, \cite{GC}, \cite{ONAG}, and \cite{WW}.
Some of the $\mathcal{P}$-positions for Chomp are given in \cite{WW}. Zeilberger \cite{TC}
and Sun \cite{IC} separately developed computer programs to find patterns for the 
$\mathcal{P}$-positions  with the top rows fixed. They proved, for the
results they got, for $n$-rowed Chomp positions, 
if the top $n - 2$ rows are fixed to certain values, 
then either there are only finitely many $\mathcal{P}$-positions, 
or when the $(n-1)$-th rows are large enough, the differences between the $(n-1)$-th rows
and the $n$-th rows are constants. While finding $\mathcal{P}$-positions is a big step
forward for analyzing Chomp, it leaves a lot of questions unanswered, and the biggest
one is how about the nim values. 
Since the $\mathcal{P}$-positions have developed into such ``gracious" patterns, 
the next natural question will be: do the nim values bear similar patterns. 
The answer is yes.

\section{Main Results}

In this article we adopt the notation [$x_1, \cdots, x_k$] for a Chomp position with $k$ rows,
and $x_1 + \cdots + x_k$ squares in the first row, $x_1 + \cdots + x_{k-1}$ the second, $\dots$, 
$x_k$ the $k$-th row.
We will also use $\{x_1, \cdots, x_k, y\}$ to represent a Chomp 
position [$x_1, \cdots, x_k$] and its nim value $y$.

\begin{thm}
\label{thm:pattern}
If we use the above notation for \{$x_1, \cdots, x_k$, $y$\}, and
\begin{displaymath}
\left\{
\begin{array}{ll}
k = 2			&	and\ x_1 < 121,\ or\ \\[2mm]
k = 3			&	and\ x_1 \le 3, x_1 + x_2 \le 5,\ or\  \\[2mm]
k = 4			&	and\ x_1 = 1, x_1 + x_2 + x_3 \le 3 \\[2mm]
\end{array}
\right.
\end{displaymath}
then $y - x_k$ is periodic for fixed [$x_1, \cdots, x_{k-1}$] when $x_k$ is large enough.
\end{thm}

Actually the Grundy function for two-rowed Chomp has a wonderful format:

\begin{thm}
\label{thm:nim}
For two-rowed Chomp positions,
\begin{displaymath}
 y = \left\{
\begin{array}{ll}
x_1 + x_2 + \lfloor \frac{x_1 - 1}{2} \rfloor	&	if\ x_2\ even \\[2mm]
\frac{3x_2 - 3}{2}								&	if\ x_2\ odd \ and \ x_2 \le x_1 \\[2mm]
x_2 + \lfloor \frac{x_1}{2} \rfloor - 1			&	if\ x_2\ odd \ and \ x_2 \ge x_1 \\[2mm]
\end{array}
\right.
\end{displaymath}
\end{thm}

\section{Proofs}

Similar to \cite{TC} and \cite{IC}, a new data structure is defined 
to calculate the nim values using Maple. Every Chomp position together with 
its nim value can be represented as a monomial in the formal power series 
\begin{displaymath}
\frac{1}{(1 - x_1) \cdots (1 - x_{k})(1-y)}
\end{displaymath}
For example, \{1, 0, 6, 4\} 
is written as $x_1 x_{3}^{6} y^4$. Since we are fixing
all the rows except one for the simplicity of calculation, 
we  have a generating 
function with only two variables
\begin{displaymath}
\frac{1}{(1-x_k)(1-y)} - 1
- \sum_{[z_1,z_2, \dots ,z_{k-1},w_1, w_2] \in \mathcal{P}} x_k^{w_1}y^{w_2}
\end{displaymath}
where [$z_1$, $z_2$, \dots, $z_{k-1}$] are the fixed top rows, 
$\mathcal{P}$ is the set of all positions and nim values generated 
by the known positions and their nim values. For instance, once we have \{1, 1, 3, 7\},
\{1, 1, $3 + \alpha$, 7\} and \{1, 1, 3, $7 + \alpha$\}, $\alpha \ge 0$ shall also 
be removed from the data structure because no other position with [1, 1] 
as the top two rows can have nim value 7, and the Chomp position [1, 1, 3] 
will not be needed for any further consideration.
Hence
\begin{displaymath}
x_3^3 y^7 (\frac{1}{1-x_3} + \frac{1}{1-y})
\end{displaymath}
will be removed from the formal power series.
The next position to be found will be the monomial 
with a positive coefficient and the 
least degree for $x$ and then $y$. Once it is found, we 
update the generating function by removing the monomials generated 
by the newly found result from the power series. 
Positions and nim values can be deducted
from the formal power series multiple times during the calculation, 
but all what it does is to change the coefficient from 1 to a negative 
number instead of 0, which does not have any effect on our result.

The program then tries to find linear relationships within the $n$-th rows 
and the nim values.
For example, results like \{1, 3, 6, 6\}, \{1, 3, 22, 22\} and \{1, 3, 38, 38\}  
suggest the formula \{1, 3, $16+6x$, $16+6x$\}. The newly generated formula
will be double-checked so that it will not conflict with previous results. 
It can be proved that if the formula is still erroneous, it can be identified and corrected,
and once no more individual positions can be found, the set of formulae found
will complete the search of nim values for the positions with the specified fixed top rows. 
The proof is presented in the Maple package.

Therefore the proof of Theorem \ref{thm:pattern} is automatically done 
by the Maple package. Unfortunately, since we are fixing the top rows
of the positions to be calculated, the Maple package was unable to find
the generized formula in Theorem \ref{thm:nim}, although it is easy to obtain by human eyes.

To  prove Theorem \ref{thm:nim} we only need to apply induction on both $x_1$ and $x_2$. 
Detailed proof is left to interested readers. Meanwhile, we give another proof from 
a different approach.

If we again adopt another set of notations used in \cite{WW} and \cite{IC}, namely for 
two-rowed Chomp positions, we denote $a$ as the number squares of the first row 
and $b$ the second, we can rewrite Theorem \ref{thm:nim} as

\begin{eqnarray}
\label{eq:y}
 y = \left\{
\begin{array}{ll}
\lfloor \frac{2 a + b - 1}{2} \rfloor	&	if\ a+b\ even \\[2mm]
min\left\{\frac{3(a - b) - 3}{2}, \lfloor \frac{2a-b}{2} \rfloor - 1 \right\}	&	if\ a+b\ odd  \\[2mm]
\end{array}
\right.
\end{eqnarray}

It definitely has similarity to the result given in \cite{WW} of finding the number of squares
$x$ in the first column to make the position a $\mathcal{P}$-position
when at most two rows can have more than one square:
\begin{eqnarray}
x = \left\{
\label{eq:x}
\begin{array}{ll}
\lfloor \frac{2 a + b}{2} \rfloor									&	if\ a + b\ even \\[2mm]
min\{ \lceil \frac{2a - b}{2} \rceil, \lceil  \frac{3(a - b)}{2} \rceil \}	&	 if\ a + b\ odd
\end{array}
\right.
\end{eqnarray}

In fact, there is intrinsic relationship between the two.
Note that chomping off all the rows except the first row is not winning unless $a = 1$, 
and chomping off all the columns except the first is not winning unless $x = 1$. 
Without those extreme conditions, we can treat the Chomp position in equation \ref{eq:x}
as two independent games: a nim game $P_1$ that consists of the bottom $x - 2$ squares, 
and a Chomp game $P_2$ [$b-1$, $a - b$], the position acquired by cutting off the first column 
from the two-rowed base [$b$, $a - b$] of the original game. 
Since no player dare to chomp to have only one column or one row left, 
and [1, 1], the Chomp position to which the original game becomes 
when $P_1$ and $P_2$ are played to the end, is a $\mathcal{P}$-position,
the players practically have to agree to play the two independent games $P_1$ and $P_2$, 
and the winning strategy is the same as the sum of two nim games: 
keep the nim values of the two separate games the same.
Therefore, to make a position in equation \ref{eq:x} a $\mathcal{P}$-position,
the nim value $y'$ for [$b-1$, $a - b$] has to be $x - 2$. And it is not hard to verify that:

When $a + b$ is even, 
$y' = \lfloor \frac{2 (a-1) + (b-1) - 1}{2} \rfloor = 
\lfloor \frac{2  a + b}{2} \rfloor - 2 = x - 2$

When $a + b$ is odd and $ a < 2b$, 
$y' = \frac{3((a-1) - (b-1)) - 3}{2} = \lceil \frac{3(a - b) - 3 - 1}{2} \rceil  = x - 2$

When $a + b$ is odd and $ a \ge 2b$, 
$y' = \lfloor \frac{2(a-1)-(b-1)}{2} \rfloor - 1 = \lceil \frac{2 a - b - 2}{2} \rceil	- 1 = x - 2$

Thus the proof is completed.

The Maple package can be downloaded at 
{\em http://www.math.temple.edu/\,$\tilde{\ }$xysun } along with some 
pre-calculated results. 
Type in {\em Help() } for help. 

\section{ Epilogue }

Due to the limitation of Maple, the author was unable to get more results for three-rowed
and four-rowed Chomp positions. However, a separate C++ program calculated three-rowed positions 
whose total number of pieces of the rows were up to 500
and suggests similar periodic relationship between the last rows and the nim values without
the benefit of the automatic proof. 
Hence it is reasonable to conjecture that the periodic relationship
exists for any given fixed top rows. Those results are also available from the website.
The limited results also failed to show any similarity between the patterns for 
the $\mathcal{P}$-positions and the Sprague-Grundy function, which should exist.

It will also be interesting to define a data structure to automatically prove 
Theorem \ref{thm:nim} using computers.

\begin{thebibliography}{2}

\bibitem[CG]{CG} R. K. Guy, (Ed.), Combinatorial Games, Proc. Symp. Appl. Math., Vol. 43, 
Amer. Math. Soc., Providence, RI, 1991.
\bibitem[CH]{CH} D. Gale, {\em A Curious Nim-type game}, Amer. Math. Monthly 81 (1974), 876-879
\bibitem[GC]{GC} Richard J. Nowakowski, (Ed.), {\em Games of No Chance}, in 
"Mathematical Sciences Research Institute Publication," Vol. 29, 
Cambridge University Press, Cabridge, U.K., 1998, 482 
\bibitem[IC]{IC} Xinyu Sun, {\em Improvements on Chomp}, to appear, Intergers Journal 
\bibitem[ONAG]{ONAG} J. H. Conway, {\em On Numbers and Games}, Academic Press, London, 1976.
\bibitem[TC]{TC} Doron Zeilberger, {\em Three-Rowed Chomp}, Adv. Appl. Math. v. 26 (2001), 168-179 
\bibitem[WW]{WW} E. R. Berlekamp, J.H. Conway, and R. K. Guy, {\em Winning Ways for 
Your Mathematical Plays}, Academic Press, London, 1982. 598-599

\end{thebibliography}


\end{document}