\documentclass[12pt]{article}
\textwidth= 6.25in
\textheight= 9.0in
\topmargin = -10pt
\evensidemargin=10pt
\oddsidemargin=10pt
\headsep=25pt
\parskip=10pt
\font\smallit=cmti10
\font\smalltt=cmtt10
\font\smallrm=cmr9

\begin{document}

\begin{center}
{\bf IMPROVEMENTS ON CHOMP}
\vskip 20pt
{\bf Xinyu Sun}\\
{\smallit Department of Mathematics, Temple University, Philadelphia, PA 19122, USA}\\
{\tt xysun@math.temple.edu}
\end{center}
\vskip 30pt
\centerline{\smallit Received: 10/16/01,
Revised: 4/29/02, Accepted: 5/17/02, Published: 5/20/02 }
\vskip 30pt

\centerline{\bf Abstract}

\noindent
The article extends the maple program in \cite{TC}
by calculating $\mathcal{P}$-positions with arbitrary number of
rows versus three rows. It also presents
a formula similar to the one in \cite{WW} by allowing the second
column to have three pieces.

\pagestyle{myheadings}
\markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL
OF COMBINATORIAL NUMBER THEORY \smalltt 2 (2002), \#G01\hfill}

\thispagestyle{empty} \baselineskip=15pt \vskip 30pt

\section*{\normalsize 1. Introduction}
%\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. Whoever eats the
poisonous one (top-left) loses. The game can also be interpreted as two players
alternately naming a divisor of a given number $N$, which may not be multiples of
previously named numbers. Whoever names 1 loses.

An example, given in \cite{WW}, shows if $N = 16 \times 27$, we have a chocolate bar
like the following:

\begin{tabular}{lllll}
1 & 2 & 4 & 8 & 16 \\
3 & 6 & 12 & 24 & 48 \\
9 & 18 & 36 & 72 & 144 \\
27 & 54 & 108 & 216 & 432 \\
\end{tabular}

Thus, naming number 24 is to eat all the squares that are multiples of 24, i.e.
the squares below and/or to the right of it.

With infinite two-dimensional Chomp, the result is obvious, the first player eats
the square at $2 \times 2$, then mimics his opponent's move by eating the same
number of squares on the $X$-axis as his opponent eats on the $Y$-axis, and vice versa.
David Gale offers a prize of \$100.00 for the first complete analysis of 3D-Chomp,
i.e. where $N$ has three distinct prime divisors, raised to arbitrary high powers \cite{GC}.
As easy and lucrative as it seems, nobody has a complete analysis of FINITE 2D-Chomp yet!

\vskip 30pt

\section*{\normalsize 2. What Do We Know}
%\section{What Do We Know}

Some trivial results can be easily seen. For example, any rectangular position is
an $\mathcal{N}$-position; any $\mathcal{P}$-position with two rows must look like
$(\alpha, \alpha-1)$ $(\alpha>1)$, i.e.
positions with $\alpha$ squares in the first row, and $\alpha - 1$ squares the second.
An $\mathcal{N}$-position
does not necessarily have a unique winning move either. For example, (3, 2, 1) has three winning moves,
(3, 1, 1), (2, 2, 1), and (3, 2).
Ken Thompson found that $4\times 5$ and $5\times 2$ both are the winning moves for $8\times 10$ \cite{WW}.

Some of the $\mathcal{P}$-positions are given in \cite{WW}. The author calculated some three-rowed
and four-rowed $\mathcal{P}$-positions with the help of computers. Doron Zeilberger gives
a computer program that finds patterns for three-rowed Chomp with the third row
fixed in \cite{TC}. The most complete result for special cases of Chomp with more than three rows
was given in \cite{WW}:
for a Chomp position with $x$ rows, and $a$ squares in the first row, $b$ squares in the
second, and one square for the rest of the rows, to be a $\mathcal{P}$-position it must have
the following form:
\begin{displaymath}
x = \left\{
\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{displaymath}

%\begin{verbatim}
% X X X X X X X X X X X X X a
% X X X X X b
% X
% X
% X
%
% x
%\end{verbatim}

%So what makes it so hard? As pointed out in \cite{TC}, it is impossible to
%find a polynomial-time algorithm for Chomp. The answer looks trivial for two-rowed
%Chomp, but impossible for the three-rowed. No matter how much we calculate with
%existing computer programs, we are still the same distance away from infinity.
%But with the help of computers, we are able to achieve something that was not
%available: large number of results that was impossible to calculate by hand, and
%they will eventually lead us to the final answer (we hope).

\vskip 30pt

\section*{\normalsize 3. Results}
%\section{Results}

In this section we adopt the notation used in both \cite{WW} and \cite{TC}, namely
we use $[a, b, c]$ to represent a three-rowed Chomp position with $a + b + c$
squares in the first row, $a + b$ in the second, $a$ in the third. So, we are writing Chomp
positions ``upside down''.

As we know, the formula for two-rowed $\mathcal{P}$-positions are trivial, i.e. $[a, 1] \ (a > 0)$. And, it looks
simple for three-rowed, with the third row fixed, since it always appears to
be [$a, b + x, c$], where
$a, b, c$ are fixed integers and $x$ is a symbolic variable for all non-negative
integers. The simplest example might be [2, $x$, 2], which characterizes [2, 0, 2],
[2, 1, 2], [2, 2, 2], [2, 3, 2] ... as $\mathcal{P}$-positions.

The author created a Maple program to calculate Chomp $\mathcal{P}$-positions of
arbitrary number of rows and columns (to the limit of computers, of course). To our pleasure,
things do get more complicated with more rows. Instead of having symbolic
variables whose coefficients are 1 as in three-rowed Chomp, we can have coefficients larger than 1.
For example, if the value of the bottom two rows of a four-rowed Chomp position
is [2, 2], it is a $\mathcal{P}$-position only when it is one of the following: [2, 2, 1, 3],
[2, 2, 2, 3], [2, 2, $3+2x$, 4], [2, 2, $4+2x$, 2]. So in this case, instead of
having one pattern for positions with a large number of squares, we have patterns
that compliment each other, and yield the final formula.

To minimize the computational complexity, we fix the bottom $k-2$ rows
of positions with $k$ rows,
and try to find the appropriate formula. As shown in \cite{TC}, we use formal
power series to calculate $\mathcal{P}$-positions. Every Chomp position can be represented
as a monomial in the formal power series $1/(1 - x_1)... (1 - x_{k})$. For example, [2, 0, 2]
will be $x_1^{2} x_2^{2} x_{3}^{4}$ (remember we are reading the Chomp positions upside down).
Now we can define weight on Chomp positions. For a position $[x_1, ... , x_{k}]$,
we define $x_{k}$ has weight 1, $x_{k-1}$ has weight 2, and so on. It is easily seen that
the weight is the exact number of squares the position has. Since we are fixing
all the rows except two, we are going to have a formal power series generating
function that requires only two variables. So we have a generating function,
\begin{displaymath}
\frac{1}{(1-x_1)(1-x_2)} - 1
- \sum_{[y_1,y_2, \dots ,y_{k-2},w_1,w_2] \in \mathcal{P}
\atop{[y_1,y_2, \dots ,y_{k-2},w_1,w_2] \in \mathcal{N}}} x_1^{w_1}x_2^{w_2}
\end{displaymath}
where [$y_1$, $y_2$, \dots, $y_{k-2}$] are the fixed bottom rows,
$\mathcal{P}$ is the set of all known $\mathcal{P}$-positions,
$\mathcal{N}$ is the set of all $\mathcal{N}$-positions derived from $\mathcal{P}$.
Once we find a new $\mathcal{P}$-position, we
update the generating function by inserting the new position into $\mathcal{P}$ and updating
$\mathcal{N}$ correspondingly. The next $\mathcal{P}$-position will be the monomial
with a positive coefficient and the
least weight. Of course, during the calculation, positions might be deducted
from the formal series multiple times, e.g. [1, 1, 1] ((3, 2, 1) if we use the original
notation), but all this does is to change the coefficient from 1 to a negative
number instead of 0, which does not have any effect on our result.

Since we do not know the coefficient $\beta$ of the patterns $\alpha + \beta x$ with $x$ as
the symbolic variable for all the non-negative integers, we have to make educated guesses
for the values in the Maple program. Whenever the program
finds a pre-defined number of positions with the same number of rows,
the values of the second rows form an arithmetic series whilst the other rows are identical,
it tries to validate the formula.
For example, positions like [2, 2, 3, 4], [2, 2, 5, 4], [2, 2, 7, 4] and [2, 2, 9, 4]
suggest the formula [2, 2, $3+2x$, 4]. The newly generated formula
will be checked against the existing $\mathcal{P}$-positions by verifying that
the formula will not create
any known $\mathcal{N}$-positions. Of course the formulas can still be erroneous and the program is capable
of correcting itself by eliminating the formula when that happens. The formulas are validated
when no more $\mathcal{P}$-positions can be generated. The life
cycle of a conjecture is completed once a formula is validated or corrected.

The computer program was written in Maple, and can be downloaded at \\
{\em http://www.math.temple.edu/\,$\tilde{\ }$xysun } along with some pre-calculated results.
Type in {\em Help() } for help. People can also play Chomp against a computer. Type in
{\em PlayChomp(POS) } where {\em POS } is the initial position. The user and computer will take
turns to name the piece they want to erase from the position. The program uses pre-calculated
results. If the computer cannot find a winning move, or if the position is beyond the range of the
results, the program will randomly eliminate a piece from the position so the game will go on.

With the help of the program, we have the following:

\noindent
{\bf Theorem 1:}
For a Chomp position with $x$ rows, $a$ squares in the first row, $b$ squares in the
second, two squares in the third, and one square for the rest of the rows,
to be a $\mathcal{P}$-position, it must satisfy the following formula:

\begin{displaymath}
x = \left\{
\begin{array}{ll}
1 & if\ a = 1 \\[2mm]
2 & if\ a = b + 1 \\[2mm]
\lfloor \frac{2 a + b}{2} \rfloor & if\ a + b\ odd\ and\ a \neq b + 1 \\[2mm]
\lfloor \frac{3 a}{2} \rfloor + 1 & if\ a = b \\[2mm]
min\{ \lceil \frac{2 a - b}{2} \rceil, \frac{3 ( a - b)}{2} \}
& if\ a + b\ even\ and\ a \neq b
\end{array}
\right.
\end{displaymath}

\noindent
{\bf Definition:} We call the {\bf height} $h$ of a Chomp position [$a_1, \dots, a_n$]
to be the number $x$ such that either
$\underbrace{[1, 0, \dots, 0, a_1-1,\dots , a_n]}_{x}$ $(x > n)$, or
[$\sum_{k=1}^{n-x+1}a_k, a_{n-x+2},\dots,a_n$] $(x \le n)$ is a $\mathcal{P}$-position,
and we write $h([a_1, \dots, a_n]) = x$.

We are trying to either chomp
the position to have only $x$ rows left, or add $x-n$ one-squared rows to the position
so that the result is a $\mathcal{P}$-position, e.g.
$h([1,0,\dots,0])=1$, $h([\underbrace{2,0,\dots,0}_{n}])=n+1$, and
$h([a_1,\dots,a_{n-1},a_{n-1}+1])=2$. The following lemma assures us the existence and
the uniqueness of the height for any Chomp position.
Let us first denote $F([a_1, \dots, a_n])$ to be the set of
followers of [$a_1, \dots, a_n$],
i.e. all the positions that can be derived
from the position by one chomp, and {\em mex}$(\{b_1, \dots, b_m\})$,
the {\em M}\,inimal {\em EX}clusion, to be the least nonnegative integer
that is {\em not} in the set $\{b_1, \dots, b_m\}$.

\noindent
{\bf Lemma 1:}
For any Chomp position $[a_1, \dots, a_n]$, $h([a_1, \dots, a_n])$ uniquely exists, and
$h([a_1, \dots, a_n]) = x$, if there exists an $x \le n$
such that [$\sum_{k=1}^{n-x+1}a_k, a_{n-x+2},\dots,a_n$] is a $\mathcal{P}$-position;
otherwise $h([a_1, \dots, a_n]) =
mex\{h([a_1', \dots, a_n'])\ |\ [a_1', \dots, a_n'] \in F([a_1, \dots, a_n])\}$.

\noindent
{\it Proof:}
The case for $x \le n$ is trivial by the definition of $h$. If such an $x$ does not exist,
and $y = mex\{h([a_1', \dots, a_n'])\ |\ [a_1', \dots, a_n'] \in F([a_1, \dots, a_n])\}$,
then $y > n$ and the followers of $\underbrace{[1, 0, \dots, 0, a_1-1,\dots , a_n]}_{y})$ are
all $\mathcal{N}$-positions by the definition of $mex$, therefore the position itself is
a $\mathcal{P}$-position. For the uniqueness part, we only have to notice that for any
two positive integers $x_1 < x_2$, the position generated by the methods above using $x_1$
is the follower of the one generated using $x_2$, thus
at most one of them is a $\mathcal{P}$-position.

Now we can rewrite the theorem as

\noindent
{\bf Theorem $1'$:}
\begin{displaymath}
h([2, b-2, a-b]) = \left\{
\begin{array}{ll}
1 & if\ a = 1 \\[2mm]
2 & if\ a = b + 1 \\[2mm]
\lfloor \frac{2 a + b}{2} \rfloor & if\ a + b\ odd\ and\ a \neq b + 1 \\[2mm]
\lfloor \frac{3 a}{2} \rfloor + 1 & if\ a = b \\[2mm]
min\{ \lceil \frac{2 a - b}{2} \rceil, \frac{3 ( a - b)}{2} \}
& if\ a + b\ even\ and\ a \neq b
\end{array}
\right.
\end{displaymath}

\noindent
{\it Proof of Theorem 1:}
Notice that the result is strikingly similar to the one given in \cite{WW}
except when $a=b$ and $a= b+1$,
and the two results compliment each other perfectly.

We denote the number of squares of the first, second, and third rows
as $\alpha$, $\beta$ and $\gamma$
respectively, and those of the first and second columns $x$ and $y$.
In our case, we only consider the positions with $y=3$ and $\gamma = 2$:

\begin{tabular}{p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}p{3mm}r}
X & X & X & X & X & X & X & X & X & X & X & X & X & & $\alpha$ \\
X & X & X & X & X & & & & & & & & & & $\beta$ \\
X & X & & & & & & & & & & & & & $\gamma$ \\
X & & & & & & & & & & & & & & \\
X & & & & & & & & & & & & & & \\
X & & & & & & & & & & & & & & \\
& & & & & & & & & & & & & & \\
x & y & & & & & & & & & & & & & \\
\end{tabular}


The first two scenarios for $x=1, 2$ are trivial and we will avoid
those cases in the discussion below. By Lemma 1, we have to consider the height of
all the followers of [$2, b-2, a-b$].

From the position, we can chomp to
\begin{eqnarray}
the\ first\ row\ up\ to \ b + 1 & & (b < \alpha < a,\ \beta = b,\ and\ \gamma = 2)
\label{eq:1} \\
the\ first\ and \ the\ second\ row & & (\alpha = \beta,\ 2 \leq \beta \leq b,\ and\ \gamma = 2)
\label{eq:2} \\
the\ second\ row\ only & & (\alpha = a,\ 2 \leq \beta < b,\ and\ \gamma = 2)
\label{eq:3} \\
the\ second\ and\ third\ row & & (\alpha = a,\ \beta = 1\ and\ \gamma = 1)
\label{eq:4} \\
the\ third\ row\ only & & (\alpha = a,\ \beta = b\ and\ \gamma = 1)
\label{eq:5}
\end{eqnarray}

By proper induction on $a$ and $b$, we can deduct the following equations:
\begin{eqnarray}
x = & min \left\{\frac{3(\alpha - b)}{2}, \left\lceil \frac{2\alpha - b}{2}\right\rceil \right\}
& if\ b < \alpha < a,\ \alpha + b\ even \label{eq:6} \\
x = & \left\lfloor \frac{2\alpha + b}{2} \right\rfloor
& if\ b < \alpha < a ,\ \alpha + b\ odd \label{eq:7} \\
x = & \left\lfloor \frac{3\beta}{2} \right\rfloor + 1
& if\ 1 < \beta \leq b \label{eq:8} \\
x = & min \left\{\frac{3(a - \beta)}{2}, \left\lceil \frac{2a - \beta}{2}\right\rceil \right\}
& if\ 2 \leq \beta < b,\ a + \beta\ even \label{eq:9} \\
x = & \left\lfloor \frac{2a + \beta}{2} \right\rfloor
& if\ 2 \leq \beta < b ,\ a + \beta\ odd \label{eq:10} \\
x = & a & \label{eq:11} \\
x = & \left\lfloor \frac{2 a + b}{2} \right\rfloor
& if\ a + b\ even \label{eq:12} \\
x = & min\left\{ \left\lceil \frac{2 a - b}{2} \right\rceil,
\left\lceil \frac{3 (a - b)}{2} \right\rceil \right\}
& if\ a + b\ odd \label{eq:13}
\end{eqnarray}
where equation \ref{eq:1} yields equations \ref{eq:6} and \ref{eq:7}, \ref{eq:2} yields \ref{eq:8},
\ref{eq:3} yields \ref{eq:9} and \ref{eq:10}, \ref{eq:4} yields \ref{eq:11},
\ref{eq:5} yields \ref{eq:12} and \ref{eq:13}

It is easy to see that $3(\alpha-\beta) \leq (2\alpha-\beta)$ iff $\alpha \leq 2\beta$

So from equation \ref{eq:6} we can have:
\begin{displaymath}
\textbf{either}\ x = \frac{3(\alpha-b)}{2}\ when\ \alpha \leq 2b\ and\ \alpha + b\ even
\end{displaymath}
which yields: ($\alpha$ is always incremented by 2 in the following arguments)
\begin{eqnarray}
x = & 3 ,\dots , \frac{3b}{2}\ incremented\ by\ 3 & if\ \ b\ even\ and\ a \geq 2b \label{eq:14} \\
& & and\ \alpha = b+2 ,\dots , 2b \nonumber \\
x = & 3 ,\dots , \frac{3(b-1)}{2}\ incremented\ by\ 3 & if\ \ b\ odd\ and\ a \geq 2b \label{eq:15} \\
& & and\ \alpha = b + 2 ,\dots , 2b-1 \nonumber \\
x = & 3 ,\dots , \frac{3(a-b-2)}{2}\ incremented\ by\ 3 & if\ a+b\ even\ and\ a \leq 2b \label{eq:16} \\
& & and\ \alpha = b + 2 ,\dots , a-2 \nonumber \\
x = & 3 ,\dots , \frac{3(a-b-1)}{2}\ incremented\ by\ 3 & if\ a+b\ odd\ and\ a \leq 2b \label{eq:17} \\
& & and\ \alpha = b + 3 ,\dots , a - 1 \nonumber
\end{eqnarray}

\begin{displaymath}
\textbf{or}\ x = \left\lceil\frac{2\alpha-b}{2}\right\rceil\ when\ \alpha \geq 2b\ and\ \alpha + b\ even
\end{displaymath}
which yields:
\begin{eqnarray}
x = & \frac{3b}{2} ,\dots , \frac{2a - b - 4}{2}\ incremented\ by\ 2
& if\ a \ even,\ b\ even \label{eq:6.2ee} \\
& & and\ \alpha = 2b ,\dots , a - 2 \nonumber \\
x = & \frac{3b + 3}{2} ,\dots , \frac{2a - b - 3}{2}\ incremented\ by\ 2
& if\ a \ odd,\ b\ odd \label{eq:6.2oo} \\
& & and\ \alpha = 2b+1 ,\dots , a - 2 \nonumber \\
x = & \frac{3b+3}{2} ,\dots , \frac{2a - b - 1}{2}\ incremented\ by\ 2
& if\ a \ even,\ b\ odd \label{eq:6.2eo} \\
& & and\ \alpha = 2b+1 ,\dots , a - 1 \nonumber \\
x = & \frac{3b}{2} ,\dots , \frac{2a - b - 2}{2}\ incremented\ by\ 2
& if\ a \ odd,\ b\ even \label{eq:6.2oe} \\
& & and\ \alpha = 2b ,\dots , a - 1 \nonumber
\end{eqnarray}

From equation \ref{eq:7}:
\begin{eqnarray}
x = & \frac{3b+6}{2} ,\dots , \frac{2a + b - 2}{2}
\ incremented\ by\ 2 & if\ a\ even\ and\ b\ even \label{eq:7ee} \\
& & and\ \alpha = b + 3 ,\dots , a - 1 \nonumber \\
x = & \frac{3b+5}{2} ,\dots , \frac{2a + b - 3}{2}
\ incremented\ by\ 2 & if\ a\ odd\ and\ b\ odd \label{eq:7oo} \\
& & and\ \alpha = b + 3 ,\dots , a - 1 \nonumber \\
x = & \frac{3b+5}{2} ,\dots , \frac{2a + b - 5}{2}
\ incremented\ by\ 2 & if\ a\ even\ and\ b\ odd \label{eq:7eo} \\
& & and\ \alpha = b + 3 ,\dots , a - 2 \nonumber \\
x = & \frac{3b+6}{2} ,\dots ,\frac{2a + b - 4}{2}
\ incremented\ by\ 2 & if\ a\ odd\ and\ b\ even \label{eq:7oe} \\
& & and\ \alpha = b + 3 ,\dots , a - 2 \nonumber
\end{eqnarray}
Note that we are avoiding the case $\alpha = \beta + 1$.

From equation \ref{eq:8} we have
\begin{equation}
x = 4,\ 5,\ 7,\ 8,\ \dots\ ,\ \left\lfloor\frac{3b}{2} \right\rfloor + 1 \label{eq:26}
\end{equation}
which are all the numbers from 4 to $\left\lfloor\frac{3b}{2} \right\rfloor$ + 1
that are {\em NOT} divisible by 3.

From equation \ref{eq:9} the result is similar to that from equation \ref{eq:6}.

From equation \ref{eq:10}
\begin{eqnarray}
x = & a + 1 ,\dots , a + \frac{b-2}{2} & if\ a\ even\ and\ b\ even \label{eq:10ee} \\
x = & a + 1 ,\dots , a + \frac{b-1}{2} & if\ a\ odd\ and\ b\ odd \label{eq:10oo} \\
x = & a + 1 ,\dots , a + \frac{b-2}{2} & if\ a\ odd\ and\ b\ even \label{eq:10oe} \\
x = & a + 1 ,\dots , a + \frac{b-3}{2} & if\ a\ even\ and\ b\ odd \label{eq:10eo}
\end{eqnarray}

Equations \ref{eq:11}, \ref{eq:12} and \ref{eq:13} result in constant numbers that require no
further discussion.

Now we can deduct our result from the equations.

Assuming $ a \geq 2b$, we have:

$x$ always covers $3 ,\dots , \lfloor \frac{3b + 2}{2} \rfloor$ from equations \ref{eq:14}, \ref{eq:15}
and \ref{eq:26}.

$x$ covers $\frac{3b+4}{2} ,\dots , \frac{2a - b - 2}{2}$ but not $\frac{2a-b}{2} = \left\lceil
\frac{2a-b}{2} \right\rceil$
if $a$ even and $b$ even from equations \ref{eq:6.2ee} and \ref{eq:7ee}. Note that the values
from the two equations are mutually exclusive, and had x covered $\frac{2a-b}{2}$, it would
have appeared in equation \ref{eq:6.2ee}, which does not.

$x$ covers $\frac{3b+3}{2} ,\dots , \frac{2a-b-1}{2} $ but not $\frac{2a-b+1}{2} = \left\lceil
\frac{2a-b}{2} \right\rceil$
if $a$ odd and $b$ odd from equations \ref{eq:6.2oo} and \ref{eq:7oo},
by similar reasoning as shown above.

All the other equations are either dealing with $a+ b $ odd, or have result bigger that
$\left\lceil \frac{2a - b}{2} \right\rceil $. So the height of the position, which is the
least number {\em NOT} in the above numbers, is $\left\lceil \frac{2a - b}{2} \right\rceil $
when $a+b$ even.

If $a$ even and $b$ odd,
$x$ covers $\frac{3b + 3}{2} ,\dots , \frac{2a - b + 1}{2}$
from equations \ref{eq:6.2eo} and \ref{eq:7eo};
$\frac{2a - b + 1}{2} ,\dots , a - 1$ from \ref{eq:9} since $a \geq 2b$;
$a$ from \ref{eq:11};
$a + 1 ,\dots , a + \frac{b - 3}{2}$ from \ref{eq:10eo}.
And the other equations are insignificant as discussed above.
So the height of the position is $a+\frac{b-1}{2} = \lfloor \frac{2a+b}{2} \rfloor$.

If $a$ odd and $b$ even, $x$ covers $\frac{3b+4}{2} ,\dots , \frac{2a - b}{2}$ from
equations \ref{eq:6.2oe} and \ref{eq:7oe};
$\frac{2a-b}{2} ,\dots , a-1$ from \ref{eq:9} since $a \geq 2b$; $a$ from \ref{eq:11};
$a+1 ,\dots , a+\frac{b-2}{2}$ from \ref{eq:10oe}.
And the other equations are insignificant as discussed above.
So the height of the position is $a+\frac{b}{2} = \lfloor \frac{2a+b}{2} \rfloor$.

Hence we have proved when $a \geq 2b$,
\begin{displaymath}
x = \left\{
\begin{array}{ll}
\left\lfloor \frac{2a + b}{2} \right\rfloor & if\ a + b\ odd \\[2mm]
\left\lceil \frac{2a-b}{2} \right\rceil & if\ a + b\ even
\end{array}
\right.
\end{displaymath}

The rest of the proof, i.e. when $a = b$ and $b < a < 2b$, is similar to the above,
and is left to the interested readers.

\vskip 30pt

\section*{\normalsize 4. Future Work}
%\section{Future Work}

It will be interesting to find out the formulas for the $\mathcal{P}$-positions with the
second columns having more than three squares or the formulas for other 3-rowed positions.
Also, since we are looking for the
$\mathcal{P}$-positions, it will be worthwhile to find out the formula
for the Sprague-Grundy function.

Finally, can we eventually claim the \$100.00 prize from David Gale?

\vskip 30pt

\section*{\normalsize 5. Acknowledgement}

Many thanks to my advisor Dr. Doron Zeilberger. Without his help, this
article would not be here. Also many thanks to the referee for his
suggestions which made this article much clearer.

\footnotesize
\begin{thebibliography}{2}

\bibitem[CH]{CH} D. Gale, {\em A Curious Nim-type game}, Amer. Math. Monthly 81 (1974), 876-879
\bibitem[GC]{GC} Richard J. Nowakowski, {\em Games of No Chance}, Cambridge University
Press, 1998, 482
\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}