\documentclass[12pt]{article} \textwidth= 6.5in \textheight= 9.0in \topmargin = -20pt \evensidemargin=0pt \oddsidemargin=0pt \headsep=25pt \parskip=10pt \font\smallit=cmti10 \font\smalltt=cmtt10 \font\smallrm=cmr9 \begin{document} \vspace*{-60pt} \centerline{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#G07} \vskip 50pt \begin{center} {\bf ON THREE-ROWED CHOMP} \vskip 20pt {\bf Andries E. Brouwer%\footnote{any footnote here} }\\ {\smallit Department of Mathematics, Technical University Eindhoven, P.O.\ Box 513, 5600MB Eindhoven, Netherlands}\\ {\tt Andries.Brouwer@cwi.nl}\\ \vskip 10pt {\bf G\'{a}bor Horv\'{a}th} {\smallit Department of Algebra and Number Theory, E\"{o}tv\"{o}s Lor\'{a}nd University, P\'{a}zm\'{a}ny P\'{e}ter s\'{e}t\'{a}ny 1/c, 1117 Budapest, Hungary}\\ {\tt ghorvath@cs.elte.hu}\\ \vskip 10pt {\bf Ildik\'{o} Moln\'{a}r-S\'{a}ska} {\tt msi@ludens.elte.hu}\\ \vskip 10pt {\bf Csaba Szab\'{o}\footnote{The research of the last 3 authors was supported by the Hungarian National Foundation for Scientific Research, Grants T043671 and T038059.}}\\ {\smallit Department of Algebra and Number Theory, E\"{o}tv\"{o}s Lor\'{a}nd University, P\'{a}zm\'{a}ny P\'{e}ter s\'{e}t\'{a}ny 1/c, 1117 Budapest, Hungary}\\ {\tt csaba@cs.elte.hu}\\ \end{center} \vskip 30pt \centerline{\smallit Received: 6/3/03, Revised: 9/20/05, Accepted: 10/16/05, Published: 11/17/05} \vskip 30pt \centerline{\bf Abstract} \noindent Chomp is a 50 year-old game played on a partially ordered set $P$. It has been in the center of interest of several mathematicians since then. Even when $P$ is simply a $3\times n$ lattice, we have almost no information about the winning strategy. In this paper we present a new approach and a cubic algorithm for computing the winning positions for this case. We also prove that from the initial positions there are infinitely many winning moves in the third row. \pagestyle{myheadings} \markright{\smalltt INTEGERS: \smallrm ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY \smalltt 5 (2005), \#G07\hfill} \thispagestyle{empty} \baselineskip=15pt \vskip 30pt \newcommand{\Nn}{{\bf N}} \newcommand{\Chompz}{Chomp${}_{\rm o}$} \section*{\normalsize 1. The game of Chomp} Chomp is a game played on a partially ordered set $P$. A move consists of picking an element $x \in P$ and removing $x$ and all larger elements from $P$. If you cannot move, you lose. %%% An equivalent formulation considers the game \Chompz~played on a partially ordered set $P_0$ with smallest element 0. A move consists of picking an element $x \in P_0$ and removing $x$ and all larger elements. If you pick $0$, you lose. %%% We shall require $P$ to be such that no infinite games are possible. That is, $P$ must not have infinite antichains, and must not have infinite descending chains. %%% In Chomp, if $P$ has a smallest element 0, then I take it, and you lose. If $P$ has a largest element 1 then the first player wins, although he may not know how. Indeed, if picking 1 is a winning move, then there is a winning move. And if picking 1 is refuted by the winning reply $x$, then the first player starts with $x$ and wins. %%% When talking about winning or lost positions it is necessary to specify for whom these positions are won or lost. A P-position is a previous player win, that is, the player to move is losing, while an N-position is a next player win. For example, in Chomp the empty poset is a P-position. %%% This game has been studied for various partially ordered sets $P$. In Sections 2 through 7 we briefly mention some previous work for certain choices of $P$. In Section 8 we present a new approach and results in the case of a $3 \times n$ lattice. If we are sloppy in the distinction of Chomp and \Chompz, it will be clear which is meant: if the poset has a smallest element and the game is supposed to last longer than one move, then we are playing \Chompz. \vskip 30pt \section*{\normalsize 2. Chomp on the Boolean lattice} Consider the lattice of all nonempty subsets of an $n$-set. It is conjectured (and was proved for $n \le 7$ by Blokhuis, Brouwer \& Doumen) that picking the top element is the winning move. More generally, Gale and Neyman [\ref{GN}] conjecture that the first player loses on the collection of all nonempty subsets of size at most $k$ in an $n$-set iff $k+1$ divides $n$. They proved this for $k = 2$. The smallest open case is $n = 7$, $k = 3$. \vskip 30pt \section*{\normalsize 3. Chomp on graphs} Take for $P$ the vertices and edges of a graph. This situation was studied by Jan Draisma and Sander van Rijnswou [\ref{Draisma}]. They show that on the complete graph $K_n$ the first player loses if and only if $n$ is divisible by 3 (reproving Gale and Neyman's result) and settled the case of forests by showing that the first player loses iff the number of vertices and the number of connected components are both even. It follows that all circuits are lost. \vskip 30pt \section*{\normalsize 4. Chomp on Platonic solids} Take for $P$ the vertices and edges and faces and body of a Platonic solid. What is the winning move? For the tetrahedron, take a vertex to leave the opponent with a $K_3$. For the other four, take the top element (the solid) and play symmetric w.r.t. the center afterwards. \vskip 30pt \section*{\normalsize 5. Chomp on a projective geometry} An example of a family of partially ordered sets with largest element where one can indicate the winning move (and a winning strategy) is that of subspaces of $PG(n,2)$, the $n$-dimensional projective geometry over the field with 2 elements. A winning move is to take a point. (Try this on the Fano plane, with seven points, seven lines, and one plane.) The proof is by induction on $n$, using a symmetry argument. Note that for $n \ge 1$ the winning move here is not the top element. \vskip 30pt \section*{\normalsize 6. Chomp on a direct product of chains} Probably the first version of this game was given by Schuh [\ref{Schuh}]. He formulated \Chompz~on the lattice of divisors of a given number $N$. Of course, if $N = \prod p^{e(p)}$ then this lattice is the direct product of chains of length $e(p)+1$. For example, for $N = 120$ we obtain the game $2\times2\times4$ Chomp. And for square-free $N$ we obtain Chomp on the boolean lattice. %%% It is easy to describe the strategy for $2\times2\times n$ Chomp. The winning move is to take the top. Let us describe a position by a quadruple $[x_{00},x_{01},x_{10},x_{11}]$, where $(i,j,x_{ij})$ is the largest element in $(i,j,*)$ for $0 \le i,j \le 1$. Now the P-positions are: $[m,m,m,m-1]$, $[m,a,b,c]$ with $a+b=m-1$ and $c=\min(a,b)$ and $1 \le m \le n$. %%% Chomp on a direct product of ordinals was studied by Scott Huddleston and Jerry Shurman [\ref{transfinite}]. They find for example that $2 \times \omega$ and $3 \times \omega^\omega$ and $2 \times 2 \times \omega^3$ and $2 \times 2 \times \omega \times \omega$ are P-positions. It is easy to see that $\Nn \times \Nn$ (that is, $\omega \times \omega$) is a first player win. It is unknown whether $\Nn \times \Nn \times \Nn$ is a first player win. \vskip 30pt \section*{\normalsize 7. Chomp on a chocolate bar} The game was reinvented by David Gale [\ref{Gale},\ref{Gale2}], who described \Chompz~on an $m\times n$ chocolate bar, that is, on the direct product of two chains. That we have \Chompz~and not Chomp is expressed by the fact that the lower left hand corner square (0,0) of the chocolate bar is poisonous. The game was baptised by Martin Gardner [\ref{Gardner}]. %%% Chomp on a $2\times n$ bar is trivial - it is a subgame of the $2\times2\times n$ game solved above - P-positions are $[m,m-1]$. %%% Chomp on a $n\times n$ square is also trivial. The first player wins: she takes (1,1), and afterwards answers symmetrically. (And the same strategy works on the infinite poset $\Nn \times \Nn$.) %%% Chomp on a $3\times n$ bar is highly nontrivial, and we will spend most of the rest of this note discussing it. \vskip 30pt \subsection*{\normalsize 7.1 Is the winning move unique?} David Gale reports that there is a unique winning move in the initial position of $3\times n$ Chomp for $n \le 100$ and also in $2\times n$, $n\times n$, $4\times 5$ and $4\times 6$ Chomp. Martin Gardner [\ref{Gardner}] described the game in a column in the Scientific American, and also asked this question. Ken Thompson from Bell Labs and M. Beeler from M.I.T discovered that the winning move need not be unique. The smallest known counterexample is $8\times 10$ Chomp. (See also [\ref{WW}], p. 598.) On the other hand, explicit computation shows that the winning move is unique in $3\times n$ Chomp for $n \le 100000$. A small Chomp position with more than one winning move is the three-rowed Chomp position $[3,2,1]$ (see below) from which one can move to either $[3,1,1]$ or $[2,2,1]$ and win. \vskip 30pt \subsection*{\normalsize 7.2 When should one take the top?} For $2\times n$ Chomp, the unique winning move is taking the top element. Gale conjectures that for $m \times n$ Chomp, with $n \ge m \ge 3$, taking the top element always loses. \vskip 30pt \section*{\normalsize 8. Three-rowed Chomp} Consider $3 \times n$ Chomp. During the play, game positions can be given by $[p, q, r]$ where $p \ge q \ge r$. If $r = 0$ then this is really $2 \times n$ Chomp, and the P-positions are those with $p = q+1$. If $r = 1$, the only P-positions are [3,1,1] and [2,2,1]. If $r = 2$, the P-positions are those with $p = q+2$. If $r = 3$, the P-positions are [6,3,3], [7,4,3] and [5,5,3]. If $r = 4$, the P-positions are [8,4,4], [9,5,4], [10,6,4] and [7,7,4]. If $r = 5$, the P-positions are [10,5,5], [9,6,5] and $[a+11,a+7,5]$ for $a \ge 0$. \vskip 30pt \subsection*{\normalsize 8.1 Recurrence relation} For given $q, r$ there is a unique $p = f(q,r)$ such that $[p,\min(p,q),\min(p,q,r)]$ is a P-position. Indeed, since for given $q,r$ there is at most one P-position $[p,q,r]$ and there are infinitely many possible $p$, it follows that for sufficiently large $x$, the position $[x,q,r]$ is an N-position with winning move in the first row, reducing $x$ to $p$ and $[x,q,r]$ to $[p,\min(p,q),\min(p,q,r)]$. Let us give a small table of $f(q,r)$ (with $q$ horizontally, and $r$ vertically). \begin{figure}[ht] \begin{center} \begin{scriptsize} \renewcommand{\tabcolsep}{0.375em} \begin{tabular}{c|cccccccccccccccccccccccccc} 24& & & & & & & & & & & & & & & & & & & & & & & & & 42 \\ 23& & & & & & & & & & & & & & & & & & & & & & & & 40 & 41 \\ 22& & & & & & & & & & & & & & & & & & & & & & & 39 & 38 & 40 \\ 21& & & & & & & & & & & & & & & & & & & & & & 37 & 38 & 36 & 39 \\ 20& & & & & & & & & & & & & & & & & & & & & 35 & 36 & 37 & 33 & 38 \\ 19& & & & & & & & & & & & & & & & & & & & 34 & 33 & 35 & 36 & 31 & 37 \\ 18& & & & & & & & & & & & & & & & & & & 32 & 33 & 31 & 29 & 35 & 34 & 36 \\ 17& & & & & & & & & & & & & & & & & & 30 & 31 & 29 & 32 & 33 & 34 & 26 & 35 \\ 16& & & & & & & & & & & & & & & & & 28 & 29 & 26 & 31 & 30 & 32 & 33 & {\bf 23} & 23 \\ 15& & & & & & & & & & & & & & & & 27 & 26 & 28 & 29 & 30 & 23 & 31 & {\bf 22} & 22 & 22 \\ 14& & & & & & & & & & & & & & & 25 & 26 & 23 & 27 & 28 & 22 & 29 & 30 & 31 & 32 & 33 \\ 13& & & & & & & & & & & & & & 24 & 23 & 22 & 25 & 26 & 27 & {\bf 19} & 19 & 19 & 19 & 19 & 19 \\ 12& & & & & & & & & & & & & 21 & 23 & 22 & 24 & 19 & {\bf 17} & 17 & 17 & 17 & 17 & 17 & 17 & 17 \\ 11& & & & & & & & & & & & 20 & 19 & 22 & 17 & 23 & 24 & 25 & 21 & 26 & 27 & 28 & 29 & 30 & 31 \\ 10& & & & & & & & & & & 18 & 19 & 20 & 21 & {\bf 14} & 14 & 14 & 14 & 14 & 14 & 14 & 14 & 14 & 14 & 14 \\ 9& & & & & & & & & & 16 & 17 & 14 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 & 30 \\ 8& & & & & & & & & 15 & 14 & 16 & 17 & {\bf 12} & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 & 12 \\ 7& & & & & & & & 13 & 14 & 12 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 & 29 \\ 6& & & & & & & 11 & 12 & 13 & {\bf 9} & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 & 9 \\ 5& & & & & & 10 & 9 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 & 27 & 28 \\ 4& & & & & 8 & 9 & 10 & {\bf 7} & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 & 7 \\ 3& & & & 6 & 7 & {\bf 5} & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 & 5 \\ 2& & & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 & 26 \\ 1& & 3 & {\bf 2} & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 \\ 0& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 & 25 \\ \hline & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 & 22 & 23 & 24 \\ \end{tabular} \end{scriptsize} \caption{Table of $f(q,r)$}\label{fig:chartpart} \end{center} \end{figure} The value of $f(q,r)$ is the smallest positive integer $p$ such that there is no move from $[p,q,r]$ to a P-position $[p',q',r']$. This gives a simple recurrence: If $r > q$, then $f(q,r) = f(q,q)$. (That is, $f$ is constant on verticals above the diagonal.) Otherwise, if $f(q-1,r) < q$, then $f(q,r) = f(q-1,r)$. (That is, if $f(q,r) = q$ then $f$ remains constant on the rest of this row.) If neither case occurs, then $f(q,r)$ is the smallest positive integer not among $f(a,r)$ for $a < q$ or among $f(q,b)$ for $b < r$. We see that $1 \le f(q,r) \le q+r+1$. This gives a cubic algorithm for computing $f(m,m)$. We computed $f(q,r)$ for $q,r \le 100000$. \vskip 30pt \subsection*{\normalsize 8.2 Periodicity} For $r = 0, 2, 5$ we see for P-positions $[p, q, r]$ that the sequence $p-q$ (indexed by $q$) is eventually periodic with period 1. For $r = 120$ it is eventually periodic with period 2. Later one finds larger periods, like period 25 for $r = 782$ and period 720 for $r = 7751$. \begin{figure}[ht] \begin{center} \begin{scriptsize} \renewcommand{\tabcolsep}{0.375em} \begin{tabular}{c|cccccccccccccccc} 122 & 240 & 241 & 242 & 178 & 243 & 244 & 245 & 175 & 246 & {\bf 174} & 174 & 174 & 174 & 174 & 174 & 174 \\ 121 & 178 & 240 & 175 & 241 & 242 & 243 & 174 & {\bf 172} & 172 & 172 & 172 & 172 & 172 & 172 & 172 & 172 \\ 120 & 175 & 238 & 240 & 239 & 172 & 242 & 241 & 244 & 243 & 246 & 245 & 248 & 247 & 250 & 249 & 252 \\ 119 & 237 & 174 & 239 & 238 & 240 & 241 & 242 & 243 & 244 & 245 & 246 & 247 & 248 & 249 & 250 & 251 \\ 118 & 236 & 237 & 238 & {\bf 168} & 168 & 168 & 168 & 168 & 168 & 168 & 168 & 168 & 168 & 168 & 168 & 168 \\ 117 & 168 & {\bf 166} & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 & 166 \\ 116 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 & 164 \\ 115 & 233 & 234 & 235 & 236 & 237 & 238 & 239 & 240 & 241 & 242 & 243 & 244 & 245 & 246 & 247 & 248 \\ 114 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 & 162 \\ \hline & 165 & 166 & 167 & 168 & 169 & 170 & 171 & 172 & 173 & 174 & 175 & 176 & 177 & 178 & 179 & 180 \\ \end{tabular} \end{scriptsize} \caption{Row 120 becomes periodic with period 2}\label{fig:period2} \end{center} \end{figure} This is the general pattern: for fixed $r$, the set of P-positions in row $r$ becomes periodic after a finite amount of initial ```junk." This beautiful periodicity theorem was proved by Steven Byrnes [\ref{Byrnes}]. \vskip 30pt \subsection*{\normalsize 8.3 Diagonal elements are largest in their column} Suppose $f(q,q)$ is not the largest number occurring in column $q$ of the table, but $f(q,r)$ with $r < q$ is the largest. Then why are none of the numbers $f(q,s)$ ($r+1 \le s \le q$) at the position $(q,r)$? Column $q$ contains $q+1$ distinct positive integers $f(q,r)$, so $f(q,r) > q$. It follows that $f(q,r)$ is the smallest element that does not occur earlier in the same row or column. Since the numbers $f(q,s)$ are not at the $(q,r)$ position, it follows that they all occur earlier in row $r$, but not at $(t,r)$ with $t \le r$ since above the diagonal verticals are constant. So, they all occur at $(t,r)$ with $r+1 \le t \le q-1$. But there are more numbers $s$ than positions $t$, a contradiction. So, $f(q,q)$ is the largest value in its column. In particular, $f(q,q) > q$. \vskip 30pt \subsection*{\normalsize 8.4 The diagonal sequence} Consider the sequence $(d_n)_n$ where $d_n = f(n,n)$ for $n \ge 0$. We find 1, 3, 4, 6, 8, 10, 11, 13, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 34, 35, 37, 39, 40, 42, 44, 45, 48, 49, 51, 53, 54, 56, 57, 59, 60, 63, 64, 66, 68, 70, 72, 73, 74, 76, 78, 80, 82, 83, 85, 87, 89, 88, 92, 93, 95, 96, 98, 100, 102, 104, 105, 107, 109, 111, 112, 113, 116, 117, 118, 121, ... (For more terms, see [\ref{Brouwer}].) This sequence is not monotonic (e.g., 89 is followed by 88): \begin{figure}[ht] \begin{center} \begin{scriptsize} \renewcommand{\tabcolsep}{0.375em} \begin{tabular}{c|cccccccccc} 55 & & & & & & & & & & 95 \\ 54 & & & & & & & & & 93 & 94 \\ 53 & & & & & & & & 92 & 91 & 90 \\ 52 & & & & & & & 88 & 91 & 90 & 92 \\ 51 & & & & & & 89 & 86 & 90 & 88 & 91 \\ 50 & & & & & 87 & 88 & 84 & 89 & 86 & 81 \\ 49 & & & & 85 & 86 & 84 & 87 & 88 & 89 & 79 \\ 48 & & & 83 & 84 & 85 & 86 & 81 & 79 & 87 & 88 \\ 47 & & 82 & 81 & 79 & 84 & 83 & 85 & 86 & 77 & 87 \\ 46 & 80 & 81 & 79 & 82 & 83 & 77 & 75 & 85 & 84 & 86 \\ \hline & 46 & 47 & 48 & 49 & 50 & 51 & 52 & 53 & 54 & 55 \\ \end{tabular} \end{scriptsize} \caption{Non-monotonicity of diagonal}\label{fig:nonmonot} \end{center} \end{figure} However, in the first 100000 terms no decrease larger than 1 occurs (and the difference between two successive terms is $-1$, 1, 2, 3 or 4, with frequencies 0.015, 0.353, 0.537, 0.085, 0.010). Let $\alpha = 1 + 1/\sqrt{2}$ (about 1.7). It looks like this sequence grows like $\alpha n$. (For $n < 100000$ we find $\alpha n - 1.242 < d_n < \alpha n + 2.141$.) \vskip 30pt \subsection*{\normalsize 8.5 Existence of constant rows} We'll call a row {\em constant} (or {\em finite}) if it is eventually constant. That is, row $r$ is a constant row when for some $q$ we have $q = f(q,r)$, and position $(q,r)$ is called the {\em start} and $q = f(q,r)$ is called the {\em value} of the constant row. The constant rows are precisely the rows $r$ for which there are only finitely many P-positions $[p,q,r]$. Every integer that does not occur on the diagonal is the value (and starting $q$) of a constant row. Indeed, we know that $[p,p,p]$ is an N-position, and a move in the bottom row leads to $[p',p',p']$, still an N-position. So, a winning move is either one in the second row, say to $[p,q,q]$, or in the third row, say to $[p,p,r]$. In the first case $p = f(q,q)$ occurs on the diagonal, in the second case $f(p,r) = p$ and $p$ is the first coordinate for the starting point of a constant row. We show that there are infinitely many constant rows. Indeed, choose $q$ such that $f(n,n) > f(q,q)$ for every $n > q$. Clearly, there are infinitely many choices for $q$. Then the number $p = f(q,q-1)$ does not occur on the diagonal (it must differ from $f(m,m)$ for $m \le q-1$, but we also have $f(q,q-1) < f(q,q) < f(n,n)$ for $n > q$) and hence occurs as the value of a constant row. Slightly more generally, if $f(n,n) > f(q,q)$ for $n > q$ and also for $q-m \le n < q$, then no number $f(q,q-i-1)$ ($0 \le i \le m$) occurs on the diagonal. Since $f(q,q) \ge q+1$ (because a diagonal element is maximal in its column), a diagonal element is not the start of a constant row. \vskip 20pt \subsection*{\normalsize 8.6 The sequence of starting points for constant rows} Consider the pairs $(q,r)$ with $f(q,r) = q$. The sequence $(q_n)_n$ (with $n \ge 1$) of first coordinates of these pairs is 2, 5, 7, 9, 12, 14, 17, 19, 22, 23, 26, 29, 31, 33, 36, 38, 41, 43, 46, 47, 50, 52, 55, 58, 61, 62, 65, 67, 69, 71, 75, 77, 79, 81, 84, 86, 90, 91, 94, 97, 99, 101, 103, 106, 108, 110, 114, 115, 119, 120, ... It is conjectured that for $3 \times n$ Chomp the winning move in the initial position is unique. (And this is true for $n < 100000$.) If this holds then the two sequences $(d_n)_n$ and $(q_n)_n$ have no elements in common, and one is the complement of the other. Let $\beta = 1 + \sqrt{2}$ (about 2.4). It looks like this sequence grows like $\beta n$. (For $n < 41420$ we find $\beta n - 1.506 < q_n < \beta n + 1.493$. The differences between successive terms were found to be 1, 2, 3, 4 or 5 with frequencies 0.116, 0.430, 0.376, 0.077, 0.0001.) %%% The sequence $(r_n)_n$ (with $n \ge 1$) of second coordinates of these pairs is 1, 3, 4, 6, 8, 10, 12, 13, 15, 16, 18, 20, 21, 23, 25, 27, 29, 30, 32, 33, 35, 37, 39, 41, 43, 44, 46, 47, 49, 50, 52, 54, 55, 57, 59, 61, 63, 64, 66, 68, 70, 71, 73, 75, 76, 78, 80, 81, 83, 85, 87, 89, 90, 92, 93, 95, 96, 98, 100, 102, 103, 105, 107, 109, 111, 113, 114, ... It looks like this sequence grows like $\alpha n$. (For $n < 41420$ we find $\alpha n - 1.853 < r_n < \alpha n + 0.780$. The differences between successive terms were found to be 1, 2 or 3, with frequencies 0.317, 0.658, 0.024.) It is unknown whether we have monotonicity here: {\it Is it true that if $f(q,r) = q$ and $f(q',r') = q'$ and $r < r'$, then $q < q'$?} \vskip 30pt \subsection*{\normalsize 8.7 Heuristics} If it is true that $d_n$ and $r_n$ behave like $\alpha n$ and $q_n$ behaves like $\beta n$ then one should expect the sequences $d_n$ and $q_n$ to be complementary: If a value $x$ occurs on the diagonal, then approximately in row $\alpha^{-1} x = (2 - \sqrt{2}) x$, about $0.6x$. If $x$ is the start of a constant row, then this happens approximately in row $\alpha \beta^{-1} x = x/\sqrt{2}$, about $0.7x$. Since $0.6x < 0.7x$, the latter would have been excluded by the former, except possibly for very small $x$. \vskip 30pt \subsection*{\normalsize 8.8 Estimates} It is possible to get a linear upper bound for $q_n$. Claim: $q_n \le 3n-1$. We have to show that if $q \ge 3n-1$ then among the numbers $f(q,r)$ there are at least $n$ that are not larger than $q$. Let us call a number $c$ a {\em constant} when it occurs as the value of a constant row, i.e., when $f(c,r) = c$ for some $r$. The claim is that there are at least $n$ constants $c \le 3n-1$. Suppose not. Pick $m = 2n-1$. There are fewer than $n$ constants $c \le 3n-1$, so looking at the $m+1$ values $f(m,r)$ we see fewer than $n$ values at most $m$, so more than $n$ values larger than $m$, and hence $f(m,m) \ge 3n$. At least $n$ of the values $1,...,3n-1$ do not occur among $f(0,0),...,f(m-1,m-1)$, but fewer than $n$ are constants, so one of these values must occur on the diagonal later, say as $f(u,u)$. We have $m < u < 3n-1$ (the latter since $f(u,u) \ge u+1$) and fewer than $n$ values $f(u,r)$ are at most $u$, so more than $u+1-n$ are larger than $u$, so that $f(u,u) \ge 2u+2-n \ge 3n+2$. But $f(u,u) \le 3n-1$ by definition, a contradiction. \vskip 30pt \subsection*{\normalsize 8.9 Encyclopedia} Sloane's encyclopedia of integer sequences [\ref{EIS}] discusses these sequences and some related ones under numbers A029899-A029905. Sequence A029899 is the number of P-positions $[p,q,r]$ with $0 \le r \le q \le p \le n$. Sequence A029900 is the diagonal sequence $(d_n)_n$. Sequence A029901 is the sequence $(q_n)_n$. Sequence A029902 is the sequence $(r_n)_n$. Sequences A029903, A029904, A029905 are defined as $p_n$, $q_n$, $r_n$ such that there exists a one-parameter family of P-positions $[k+p_n+q_n, k+q_n, r_n]$ for $k = 0,1,2,..$. Sloane mentions the conjecture that Sequence A029905 is complementary to Sequence A029902, that is, that every row either becomes constant or becomes periodic with period 1. As we have seen, this is false, and 120 is the smallest number that is neither in A029902 nor in A029905. \vskip 30pt \subsection*{\normalsize 8.10 Element frequencies} We find that if $c = q_n$ and $c < 100000$, then there are precisely $n$ pairs $(q,r)$ with $q < c$ and $f(q,r) = c$. These pairs have $c-n \le q \le c-1$. For the diagonal elements there is approximate linear behaviour: $d_n$ occurs approximately $n/2$ times. \vskip 30pt \subsection*{\normalsize 8.11 Row minima} Let $m_r = \min \{ f(q,r) | q > r \}$, and let $k_r$ be the (smallest) $q$ for which $f(q,r) = m_r$. Claim: {\it The sequence $m_r$ is non-decreasing.} Consider the position $(k,s)$ where $s > r$ and $k \le k_s$. The value $f(k,s)$ differs from the values earlier in column $k$ and from the diagonal values $f(m,m)$ with $m < s$. If $f(k,s) < m_r$, then the value $f(k,s)$ was not excluded at the $(k,r)$ position: it differs from earlier elements on diagonal and column, and also differs from the other row elements since it is smaller. This is a contradiction. So, $m := \min(m_s, f(s,s)) \ge m_r$. Suppose we have equality, and pick $k$ minimal so that $m = f(k,s)$. Since $m$ was not found at the $(k,r)$ position, we must conclude that $k > k_r$. This shows that when row minima stay the same, the column in which they occur increases. If a row minimum is the start of a constant row, that is, when $m_r = f(k,r)$ with $k = m_r$, then $m_s > m_r$ for $s > r$ since the constant row blocks all further columns. It is unknown whether the start of a constant row must be the off diagonal row minimum. This question is equivalent to that about monotonicity of the set of $(q,r)$ forming the start of a constant row. If it is true that the start $p$ of a constant row must be the off diagonal row minimum, then it follows that it cannot occur on the diagonal (not earlier, because that would exclude $p$, and not later because the constant row is the last row in which $p$ occurs). Thus, under this assumption $f(p,r) = p$ and $f(q,q) = p$ cannot both hold, and the winning move in $[p,p,p]$ is unique. \vskip 30pt \subsection*{\normalsize 8.12 Summary} We investigated the $3\times n$ Chomp by introducing a function of two variables which describes the P-positions. This function can be displayed in a two-dimensional chart, and the investigation of this chart is equivalent to the investigation of $3\times n$ Chomp. With the analysis of this chart we obtained several results for the game easily, e.g., there are infinitely many winning moves in the third row. Several questions remain open for the $3\times n$ Chomp. The most interesting one is to prove that there is a unique winning move from the initial position. For this it is enough to prove that the series $d_n$ and $r_n$ are asymptotically $\alpha n$ and $q_n$ is asymptotically $\beta n$ for $\alpha=1+\frac1{\sqrt{2}}$ and $\beta=1+\sqrt{2}$. Another open problem is to prove the monotonicity of $f(q,r)$, which is equivalent to the uniqueness of the winning move from the initial position, and also equivalent to the statement that every start of a constant row must be the off diagonal row minimum. \vskip 30pt \section*{\normalsize References} \footnotesize \renewcommand{\labelenumi}{[\theenumi]} \begin{enumerate} \item\label{WW} Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, {\it Winning Ways}, Academic Press, London, 1982, pp. 598-601. \item\label{Brouwer} Andries E. Brouwer, {\it The game of Chomp}.\\ {\tt \verb#http://www.win.tue.nl/~aeb/games/chomp.html#} \item\label{Byrnes} Steven Byrnes, {\it Poset game periodicity}, INTEGERS Electr. J. Combin. Number Th. {\bf 3} (2003). \item\label{Draisma} Jan Draisma and Sander van Rijnswou, {\it How to chomp forests, and some other graphs}, 2002.\\ {\tt \verb#http://www.math.unibas.ch/~draisma/recreational/graphchomp.pdf#} \item\label{Gale} David Gale, {\it A curious Nim-type game}, Amer. Math. Monthly {\bf 81} (1974) 876--879. \item\label{Gale2} David Gale, {\it A curious Nim-type game}, Appendix 1 in: Tracking the Automatic Ant, Springer, New York, 1998. ISBN: 0-387-98272-8. \item\label{GN} D. Gale and A. Neyman, {\it Nim-type games}, Internat. J. Game Theory {\bf 11} (1982) 17--20. \item\label{Gardner} Martin Gardner, {\it Mathematical Games}, Scientific American, Jan. 1973, pp. 110--111. (See also ibid. May 1973.) \item\label{transfinite} S. Huddleston and J. Shurman, {\it Transfinite Chomp}, pp. 183--212 in: More Games of No Chance, Proc. MSRI Workshop on Combinatorial Games, July, 2000, Berkeley, CA, MSRI Publ. (R. J. Nowakowski, ed.), Cambridge University Press, Cambridge, 2002. ISBN: 0-521-80832-4. \item\label{Schuh} Fred. Schuh, {\it Spel van delers}, Nieuw Tijdschrift voor Wiskunde {\bf 39} (1952) 299--304. \item\label{EIS} N.J.A. Sloane, {\it Encyclopedia of Integer Sequences}.\\ {\tt \verb#http://www.research.att.com/~njas/sequences/index.html#} \end{enumerate} \end{document}