CHOMP, RECURRENCES, and CHAOS(?)

Doron ZEILBERGER ^{1}

Dedicated to Saber Elaydi on his 60th Birthday

Abstract. In this article, dedicated with admiration and friendship to Chaos and Difference (and hence Recurrence) Equations Guru Saber Elaydi, I give a new approach and a new algorithm for Chomp, David Gale’s celebrated combinatorial game. This work is inspired by Xinyu Sun’s “ultimate-periodicity” conjecture and by its brilliant proof by high-school-student Steven Byrnes. The algorithm is implemented in a Maple package BYRNES accompanying this article. By looking at the output, and inspired by previous work of Andries Brouwer, I speculate that Chomp is Chaotic, in a yet-to-be-made-precise sense, because the losing positions are given by “weird” recurrences.

Saber Elaydi

When Gerry Ladas asked me to write an article dedicated to Saber Elaydi, I hesitated, since while we both work on difference equations, our research interests (but not our mathematical philosophies!) are almost diametrically opposite. In particular, the subject of my current research, Combinatorial Games, seemed superficially to be far removed from Saber’s research interests. On further thought, however, I realized that this current research of mine is not as far from Saber, after all, since recurrences feature in it prominently. But recurrence equations are almost synonymous with difference equations (see the next section), and Saber wrote the Book[E1] on this subject, a modern classic that I, and my students, thoroughly enjoyed. As I dwelt even deeper into my research, I also realized that chaos, or something like it, also arises naturally, and Saber is also a Chaos guru (cf. [E2]). So even though the primary “subject classification” of this article is “Combinatorial Games”, the secondary ones are “Recurrence equations” and “Chaos”, so I hope that Saber will find this interesting. Happy 60th Birthday, Saber!

Difference vs. Recurrence Equations

In most contexts, the notions of difference equation and of recurrence equation are identical, and the choice of which of them to use is merely cultural, the former preferred by numerical analysts and the latter by combinatorialists and number theorists.

Indeed a generic form for an r^{th}-order difference equation is

P (n, f(n), Δf(n), Δ^{2}f(n), …, Δ^{r}f(n)) ≡ 0 ,

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. zeilberg@math.rutgers.edu http://www.math.rutgers.edu/~zeilberg/ . First version: June 3, 2003. This version: June 9, 2003. Accompanied by the Maple package BYRNES available from http://www.math.rutgers.edu/~zeilberg/programs.html .

Supported in part by the NSF.

while a generic form for an r^{th}-order recurrence equation is

Q(n, f(n), Ef(n), E^{2}f(n), E^{r}f(n)) ≡ 0 ,

where, as usual, Δf(n) := f(n+1)−f(n) and Ef(n) := f(n+1). Since Δ = E −1 and E = Δ+1, we can write, using the binomial theorem , Δ^{k}f(n) = (E − 1)^{k}f(n) as a linear combination of E^{i}f(n)’s and E^{k}f(n) = (Δ + 1)^{k}f(n) as a linear combination of Δ^{i}f(n)’s, thereby going from one form to the other.

This equivalence is still true if the order of the difference (alias recurrence) equation is infinite (i.e. to compute f(n) we need all the previous values: f(n − 1), f(n − 2), …, f(1), f(0), but only if the function P is “algebraic” or “analytic” in some sense. In this article we will encounter weird recurrences that in addition to using all the previous values, also feature mex that inputs sets of integers and outputs non-negative integers.

Definition of mex: Given a set of non-negative integers S, mex(S) is the smallest non-negative integer that does not belong to S.

For example, mex({0, 1, 2, 5, 7}) = 3, and mex({2, 3, 5, 7}) = 0.

Beware of Sequences Defined by mex

Exercise: Consider the sequence defined by the recurrence

a_{i} := mex({0, 1} ∪ {ja_{r} ; j ≥ 1 , 1 ≤ r < i}) , i ≥ 1 .

Prove some obvious properties of this sequence, for example that there are infinitely many i with a_{i+1} − a_{i} = 2.

How To Play CHOMP

David Gale’s famous game of Chomp ([G]) starts out with an M by N chocolate bar, in which the leftmost-topmost square is poisonous. Players take turns picking squares. In his or her (or its) turn, a player must pick one of the remaining squares, and eat it along with all the squares that are “to its right and below it”. Using matrix-notation with the poisonous square being entry (1, 1), and the initial position consisting of the whole bar {(i, j) ; 1 ≤ i ≤ M, 1 ≤ j ≤ N}, then picking the square (i_{0}, j_{0}) means that one has to eat all the remaining squares (i, j) for which both i ≥ i_{0} and j ≥ j_{0} hold. The player that eats the poisonous (leftmost-topmost) square loses. Of course picking (1, 1) kills you, so a non-suicidal player will not play that move unless it is forced to.

For example, if M = 4 and N = 3, then the initial game-position is

\begin{matrix}X & X & X \\ X & X & X \\ X & X & X \\ X & X & X \end{matrix} .

The first player may choose to play (4, 3), in which case the game-position becomes

\begin{matrix}X & X & X \\ X & X & X \\ X & X & X \\ X & X \end{matrix} ,

or he may choose to play (2, 2), which shrinks the chocolate bar to

\begin{matrix}X & X & X \\ X \\ X \\ X \end{matrix} ,

and so on.

What is Chomp Good For?

Chomp is a typical example of a combinatorial game. The mathematical theory of combinatorial games is one of the most gorgeous subjects in the whole of mathematics, see [BCG] and [F] for nice expositions. Why study Combinatorial Games? If beauty is not a good enough reason for you, then there are numerous other reasons, since according to Steven Byrnes [By], “Combinatorial game theory has applications in fields such as complexity theory, artificial intelligence, error-correcting codes, algorithms, and surreal analysis, and of course, human recreation (chess, for example).” All true, of course, but Byrnes forgot to mention an even more important application, at least for the Byrnes family. It can pay your Harvard tuition! ([By] won first prize at the 2002 Siemens Westinghouse Competition, worth a $10^{5} scholarship).

Chomp Positions

Any Chomp position in a game that starts out with an M × N chocolate bar, can be described by an array of integers (a_{1}, a_{2}, …, a_{M}), with N ≥ a_{1} ≥ a_{2} ≥ … ≥ a_{M} ≥ 0. We will find it more convenient to set b_{i} = a_{i} − a_{i+1} for 1 ≤ i < M and b_{M} = a_{M}, and denote the same position with square brackets, and read it from bottom to top [b_{M}, b_{M−1}, …, b_{1}]. Note that this means that there are b_{i} columns with exactly i squares. The advantage of this notation is that the b_{i} are independent non-negative integers.

3-Rowed Chomp

This was studied in my previous article [Z], whose “meta-motivation” was to give an example of “computer-generated research”, where the computer first conjectures a pattern, and then proves it rigorously, all by itself. This work was extended, using both human and computer ingenuity by my student Xinyu Sun[S], first for computing the so-called Sprague-Grundy function (a.k.a. nim-values ), and then for general Chomp, in which all but the two top-rows are fixed. Xinyu Sun[S] conjectured that the set of losing positions (and more generally the set of positions with any given nim-value) is either a finite set, or displays “ultimately-periodic” behavior, in a sense described below. This was further confirmed empirically, for the case of 3-rowed Chomp, by Andries Brouwer[Br] for the bottom row as large as 90000. Brouwer also refuted the implicit conjecture in [Z] that for 3-rowed Chomp the period is always one (i.e. that the sequence is ultimately-constant). Brouwer found that when the bottom row has exactly 120 squares, then the period is 2, and found many other examples of larger periods later on.

Enter Steven Byrnes

But neither I, nor Xinyu Sun, nor Andries Brouwer, were able to prove Sun’s ultimate-periodicity conjecture. Steve Byrnes’s prize-winning article [By] is truly impressive!

In spite of Byrnes’s breakthrough, the following is still open.

BIG PROBLEM: Give A fast (i.e. poly-log in c + a + b ), characterization of the set of losing Chomp positions [c, a, b].

Here I only consider the following more modest problem, already studied in [Z].

LITTLE PROBLEM: For any inputted integer C give a fast (poly-log in a + b) characterization of the set of losing Chomp positions [c, a, b], with c ≤ C.

In [Z], the little problem was solved for C = 115, and the algorithm could be extended, in principle, for any C, as long as the ultimate-periodicity phenomenon holds. Before Byrnes, we did not know for sure that it would always work, but now we do!

So why bother with yet another paper and yet another Maple package? First, our new Maple package BYRNES accompanying this paper, is much more efficient than the Maple package Chomp3Rows that accompanied [Z]. Second, BYRNES also computes Grundy function tables automatically. Third, this paper gives an easy algorithmic proof of Byrnes’s theorem, much easier to follow than Byrnes’s original proof. Finally, and most importantly, it is yet another example of ‘taming the infinite’ and using computers to discover and prove general theorems (i.e. infinitely many facts) by finitary means.

Set of Positions and Legal Moves

A combinatorial game is completely determined by its set of legal positions, S, and by a set-valued function f : S → 2^{S}, assigning to any member of S a (possibly empty) subset of S where f(s) is the set of positions reachable from s in one move.

For 3-rowed Chomp we have

S := {[c, a, b] ; a, b, c ≥ 0}\{[0, 0, 0]} ,

and

f([c, a, b]) := {[c, a, b − x] ; 0 < x ≤ b}
∪ {[c, a − x, 0] ; 0 < x ≤ a}

∪ {[c − x, 0, 0] ; 0 < x < c}
∪ {[c, a − x, b + x] ; 0 < x ≤ a}
∪ {[c − x, 0, a + b + x] ; 0 < x ≤ c}
∪ {[c − x, a + x, b] ; 0 < x ≤ c} .  (LegalMoves)

The six sets on the right hand side of (LegalMoves) correspond to chomping, respectively, at the top row, “columns of 1’s section”, top row, “columns of 2’s section”, top row, “columns of 3’s section”. middle row, “columns of 2’s section”, middle row, “columns of 3’s section”, and bottom row, “columns of 3’s section” .

This description is equivalent to the usual description in terms of a directed graph. The set of vertices is S and f(s) = {t|s → t}.

Yet another description of a game, more useful for our purposes, is to state the sets g(t) := {s|s → t}, in other words for each position t, indicate those positions from which t can be reached in one (legal) move.

In the case of 3-rowed Chomp we have

if a, b > 0 then

g([c, a, b]) = {[c, a, b+x] ; x > 0} ⋃ {[c, a+x, b−x] ; 0 < x ≤ b} ⋃ {[c+x, a−x, b] ; 0 < x ≤ a} , (Rule1)

while if a > 0 and b = 0 then

g([c, a, 0]) = {[c, a + x, y] ; x ≥ 0, y ≥ 0, x + y > 0} ⋃ {[c + x, a − x, 0] ; 0 < x ≤ a} , (Rule2)

while if b > 0 and a = 0 then

g([c, 0, b]) = {[c + x, y, b − x − y] ; x ≥ 0, y ≥ 0, 0 < x + y ≤ b} ,  (Rule3)

and, finally when a = 0 and b = 0 then

g([c, 0, 0]) = {[c + x, y, z] ; x ≥ 0, y ≥ 0, z ≥ 0, 0 < x + y + z} .  (Rule4)

We have the following consequences.

Lemma 1:

if a, b > 0 and [c, a, b] is a loser then the following are guaranteed winners

{[c, a, b + x] ; x > 0}  (1.1)
{[c, a + x, b − x] ; 0 < x ≤ b}  (1.2)
{[c + x, a − x, b] ; 0 < x ≤ a} .  (1.3)

Lemma 2: If a > 0 and [c, a, 0] is a loser then the following are guaranteed winners

{[c, a + x, y] ; x ≥ 0 , y ≥ 0 , x + y > 0} .  (2.1)
{[c + x, a − x, 0] ; 0 < x ≤ a} .  (2.2)

Lemma 3: If b > 0 and [c, 0, b] is a loser then the following are guaranteed winners

{[c + x, y, b − x − y] ; x > 0 , y > 0 , 0 < x + y ≤ b} .

The ‘Trivial’ Case of 2-Rowed Chomp

2-rowed Chomp is really a piece of cake. Instead of using a real chocolate bar, we can play this game on the lattice N^{2} with [0, 0] removed. The Chomp position [a, b] can be thought of the location of a counter. There are three kinds of legal moves:

[a, b] → [a, b − x] , 1 ≤ x ≤ b  (LegalMove1)
[a, b] → [a − x, b + x] , 1 ≤ x ≤ a  (LegalMove2)
[a, b] → [a − x, 0] , 1 ≤ x < a .  (LegalMove3)

If a player can’t move (i.e. it is at position [0, 1]), then it lost. Henceforth we will call positions “points”, and refer to “losing positions” and “winning positions” as losers and winners respectively.

Once we know that [a, b] is a loser, we know right away many winners, namely all those points from which [a, b] may be reached in one move, i.e. using any of (LegalMove1 − 3). It follows that we have the

Implied Winners Lemma: If [a, b] is a loser, and b > 0, then

[a, b + x] , 1 ≤ x < ∞ ,  (ImW 1)
[a + x, b − x] , 1 ≤ x ≤ b ,  (ImW 2)

are all winners. If [a, 0] is a loser then

[a + x, y] , 0 ≤ x, y < ∞ , x + y > 0 ,  (ImW 3)

are all winners.

Let’s try to find the set of losers in 2-rowed Chomp. We already know that [0, 1] is a loser, hence by (ImW 1), [0, x], x > 1 are winners, and so is [1, 0], by (ImW 2). Crossing out [0, 1] and all its implied winners, the minimal point is [1, 1] that must be a loser since it only leads to previously established winners. Now [1, 1]’s implied winners are [1, x], x > 1, and [2, 0], and hence [2, 1] is a loser. By induction, if [a, 1] is a loser, then [a, x], x > 1 and [a + 1, 0] are winners, and hence the minimal uncovered point, [a + 1, 1], is a loser, since it only leads to [a + 1, 0] [a + 1 − x, x + 1], (x ≥ 1), and [x, 0] (x ≤ a), which are all previously established winners. It follows that we have the “theorem” that the set of losing positions in 2-rowed Chomp is {[a, 1] ; a ≥ 0}.

2-Rowed Chomp with Instant Winners

Now consider a slight generalization. The positions and legal moves are the same, but, by fiat, the members of a certain (finite or infinite) set of points are designated instant winners, and if it is your turn to move, and the counter is on that point, you are declared the winner.

Let’s describe this set (of points [a, b]) as a sequence of sets (of integers), I_{a} (0 ≤ a < ∞), where I_{a} is the set of b such that [a, b] is an instant winner. If the set of instant winners is finite then there would be an a_{0} such that I_{a} = ∅, for a ≥ a_{0}, in other words I_{a} would be eventually the empty set.

Let’s try to figure out how to determine the set of losers, in this, more general, game. Because of (ImW 1) it follows that for any given a there is at most one b such that [a, b] is a loser. Let’s denote it by L_{a}, if it exists. Because of (ImW 3), it follows that if [a_{0}, 0] is a loser then there are no losers with a > a_{0}. In this case there are only finitely many losers.

The problem of finding the set of losers is equivalent to determining the sequence of integers {L_{a}}_{a=0}^{∞}. Fix an integer a, and suppose that we already know L_{i} for i < a. This means that [i, L_{i}] are losers for 0 ≤ i < a. Because of (ImW 2),

[a, L_{i} − (a − i)] , 0 ≤ i < a

are implied winners. Combining these winners-by-merit with the lazy instant winners, it follows that L_{a} is the smallest non-negative integer that is not in the set

I_{a} ∪ {L_{a−1} − 1, L_{a−2} − 2, …, L_{0} − a} .

In particular if L_{i} exists for i < a and is never 0, then L_{i} exists. We have just established the

Fundamental Recurrence for Two-Rowed Chomp with Instant Winners

Let {I_{a}}_{a=0}^{∞} be a sequence of sets of non-negative integers. Consider 2-rowed Chomp with the set of Instant Winners

⋃_{a=0}^{∞}{[a, b] ; b ∈ I_{a}} .

Then the set of losers is the set {[a, L_{a}] ; a ≥ 0}, where L_{a} is given by the Recurrence

L_{a} = mex(I_{a} ∪ {L_{a−1} − 1, L_{a−2} − 2, …, L_{0} − a}) ,  (F undamentalRecurrence)

valid as long as L_{a} > 0. If and when L_{a_{0}} = 0, then the sequence {L_{a}}_{a=0}^{∞} terminates at a = a_{0}. Example: Suppose that the set of instant winners consists of [0, 0], [0, 1], [0, 2], [0, 3], [1, 0], [1, 1], [1, 5], and [a, 0], [a, 1] (a > 1). In other words I_{0} = {0, 1, 2, 3}, I_{1} = {0, 1, 5} , I_{a} = {0, 1}(a ≥ 2). We have:

L_{0} = mex(I_{0}) = mex({0, 1, 2, 3}) = 4 ,
L_{1} = mex(I_{1} ∪ {L_{0} − 1}) = mex({0, 1, 3, 5}) = 2 ,
L_{2} = mex(I_{2} ∪ {L_{1} − 1, L_{0} − 2}) = mex({0, 1, 2}) = 3 ,
L_{3} = mex(I_{3} ∪ {L_{2} − 1, L_{1} − 2, L_{0} − 3}) = mex({0, 1, 2}) = 3 ,
L_{4} = mex(I_{4} ∪ {L_{3} − 1, L_{2} − 2, L_{1} − 3, L_{0} − 4}) = mex({0, 1, 2}) = 3 .

Now we can already guess a pattern, L_{a} = 3 for a ≥ 2. Let’s try and prove it by induction using (F undamentalRecurrence). We have just established it for a = 2, 3, 4. For a ≥ 5 we have, by the inductive hypothesis, that the set of non-negative integers in

I_{a} ∪ {L_{a−1} − 1, L_{a−2} − 2, …, L_{0} − a}

is really finite, namely

I_{a} ∪ {3 − 1, 3 − 2, 3 − 3} = {0, 1, 2}

and its mex equals 3. The Ultimate-Periodicity Phenomenon Now assume that the sequence of sets I_{a} describing the instant winners is not arbitrary, but is ultimately-periodic. In other words, starting at a certain place a_{0}, there is a (minimal) period p such that I_{a} = I_{a+p} for a > a_{0}. Now we are on more secure grounds. Ultimately-Periodic Sequences are finite objects, and hence meaningful. To describe such a sequence all we have to do is specify the non-periodic head I_{0}, …, I_{a_{0}} followed by the period I_{a_{0}+1}, I_{a_{0}+2}, …, I_{a_{0}+p} that keeps repeating. Two Immediate Consequences of (F undamentalRecurrence) Lemma Bounded: If the sets I_{a} are (uniformly) bounded, and M − 1 is an upper bound, (i.e. max(I_{a}) ≤ M − 1 for all a > 0) then L_{a} ≤ M, for all a > 0. Proof: This follows immediately from the fact that mex(S) ≤ max(S) + 1, and induction on a.

Ultimate-Periodicity Theorem: If I_{a} is ultimately-periodic then the sequence L_{a} either terminates (with the last value being 0), or else is ultimately-periodic.

Proof: Since I_{a} is ultimately-periodic the set of finite sets {I_{a} ; a > 0} is finite, and hence bounded. Let M −1 be the (least) upper bound. By Lemma Bounded, L_{a} ≤ M. Since negative integers in a set do not affect its mex (recall that mex(S) is the smallest non-negative integer in the complement of S), the hitherto “infinite memory” recurrence (F undamentalRecurrence), where to know the value of L_{a} you have to remember all your past, now becomes a “finite memory” recurrence, where you only have to remember what happened in the last M days.

L_{a} = mex(I_{a} ∪ {L_{a−1} − 1, L_{a−2} − 2, …, L_{a−M} − M}) . (BoundedF undamentalRecurrence)

Introducing the ‘states’

S_{a} := (I_{a} ; L_{a−1}, L_{a−2}, …, L_{a−M})

(BoundedF undamentalRecurrence) induces a well-defined function F := S_{a} → S_{a+1}. Since L_{a} is bounded, and I_{a} is ultimately-periodic, it follows that there are only finitely many states. By the venerable Pigeon-Hole Principle, sooner or later we must visit a previously-visited ‘state’, i.e. there exists an a_{0} and a q such that S_{a_{0}} = S_{a_{0}+q}. But once that happens, everything repeats itself with period q, and S_{a_{0}} = S_{a_{0}+iq} for all i > 0. In particular, L_{a+q} = L_{a} for all a ≥ a_{0} + 1.

A Posteriori Justification

How to turn this into an algorithm? The ‘theoretical’ upper bound for the period is enormous, but is hardly (and perhaps never) achieved. Once an ultimately-periodic sequence of sets I_{a} is given in the form

[I_{0}, I_{1}, …, I_{b_{0}}][I_{b_{0}+1}, I_{b_{0}+2}, …, I_{b_{0}+p}]^{∞} ,

just keep computing L_{a} using (BoundedF undamentalRecurrence). Suppose that your computer detects that, after a certain place a_{0}, the same segment L_{a_{0}+1}, L_{a_{0}+2}, …, L_{a_{0}+q} keeps repeating (say 10 times). Then the computer is justified in guessing that the {L_{a}}_{a=0}^{∞} equals.

[L_{0}, L_{1}, …, L_{a_{0}}][L_{a_{0}+1}, L_{a_{0}+2}, …, L_{a_{0}+q}]^{∞} .

In order to prove this conjecture you only have to check it for the finite number of cases 0 ≤ a ≤ max(a_{0}, b_{0}) + M + lcm(p, q), since later on things start to ‘repeat themselves’.

Analogy Example 1: Guess the decimal representation of 1/3, and then prove it rigorously.

Solution: Compute 1/3 to ten-decimal-digits accuracy, guess that 1/3 = 0.3333333333 …, and then prove it rigorously by summing an infinite geometric series:

3 ∑_{i=1}^{∞}(1/10)^{i} = 3\frac{1}{10 − 1} = \frac{1}{3} .

Analogy Example 2: Guess the continued-fraction representation of \sqrt{7}, and then prove it rigorously.

Solution: Using Maple, or, if you wish, pencil-and-paper, compute convert(evalf(sqrt(7)),confrac);, getting [2,1,1,1,4,1,1,1,4,1,1,1,4,1,1,1,4]. Now conjecture that \sqrt{7} = [2, (1, 1, 1, 4)^{∞}]. Let’s call the right side x. Then x = 2 + 1/y, where y = [(1, 1, 1, 4)^{∞}]. This means y = 1 + 1/(1 + 1/(1 + 1/(4 + 1/y))), from which you can get a quadratic equation satisfied by y, that implies the quadratic equation satisfied by x, that turns out to be x^{2} − 7 = 0.

Note that the current algorithm for proving the conjectured ultimately-periodic sequence L_{a} from the input ultimately-periodic sequence of Instant Winners I_{a} is perfectly valid even if we did not have the a priori assurance that it is always guaranteed to work. The Ultimate-Periodicity Theorem guarantees that we are bound to succeed at the end, even though some of our initial guesses may prove to be wrong.

This is also true in the two elementary ‘analogy examples’ above. A well-known, elementary, and very easy theorem (that uses the pigeon-hole principle!) asserts that any rational number has either a terminating or an ultimately-periodic decimal expansion. This guarantees that the ‘empirical algorithm’ is going to work for any rational number.

Analogously for Example 2. A theorem of Lagrange states that any quadratic irrationality has an ultimately-periodic continued fraction, and the proof also uses recurrences and the pigeon-hole principle. Hence we have an a priori guarantee that this will work for the square-root of any (non-perfect-square) integer.

Back to Three-Rowed Chomp

Recall our Little Problem of determining fast, all the losers [c, a, b] for c ≤ C, where C is a fixed, given integer.

Because of the first part of (Rule1), it follows that for any given c and a, there is at most one b such that [c, a, b] is a losing position. Let’s define B_{c}(a) to be that b (if it exists, otherwise it is undefined).

It follows that knowledge of the set of losers in 3-rowed Chomp is the same as knowing the sequence of sequences B_{c}, and knowing it for c ≤ C is the same as knowing its first C + 1 terms.

We already know B_{0}! This is just the case of 2-rowed Chomp, and we found that B_{0} = 1^{∞}. Suppose that we already know B_{c} for c < C and are interested in B_{C}. Now observe that B_{C} is just the loser-sequence for a 2-rowed Chomp (since the c is fixed at C) with lots of Instant Winners! These Instant Winners are those positions implied by losers from c < C via (1.3), (2.2) and Lemma 3.

So let’s define the sequence of those Instant Winners W_{C}(a) as the set of b such that [C, a, b] is a winner implied by some L_{c} with c < C. W_{C}(a) can be naturally partitioned as

W_{C}(a) = ⋃_{c=0}^{C−1} V_{C,c}(a) ,

where V_{C,c}(a) is the set of b such that [C, a, b] is reachable from some loser [c, a′, b′]. V_{C,c}(a), in turn, can be written conveniently as

V_{C,c}(a) = V′_{C,c}(a) ∪ V′′_{C,c}(a),

where V′_{C,c}(a) is the contribution from Lemma 3, and V′′_{C,c}(a) is the contribution from (1.3) and (2.2). From Lemma 3, (1.3), and (2.2), we have, Crucial Facts for a ≥ 0:

V′_{C,c}(a) = {B_{c}(0) − (C − c) − a} ∩ Z_{≥0} ,
V′′_{C,c}(a) = {B_{c}(a + C − c)} .

Note that each of these sets is either empty or a singleton. We are now ready to give a new proof of Byrnes’s Theorem: For every C, B_{C} is ultimately-periodic. Proof: By the Ultimate-Periodicity Theorem it suffices to show that for each non-negative integer C, the sequence of sets {W_{C}(a)}_{a=0}^{∞} is ultimately-periodic. Note that if {S(a)}_{a=0}^{∞} and {T (a)}_{a=0}^{∞} are ultimately-periodic sequences of sets so is

{(S ∪ T)(a)}_{a=0}^{∞} := {S(a) ∪ T (a)}_{a=0}^{∞} .

We proceed by induction on C. We already know that it is true for C = 0. By induction, the sequence of sets {V′′_{C,c}(a)}_{a=0}^{∞} is ultimately-periodic, and {V′_{C,c}(a)}_{a=0}^{∞} is even better, it is ultimately empty. Hence their union, {V_{C,c}(a)}_{a=0}^{∞} is ultimately-periodic for all c < C, and hence so is their point-wise union over c < C, {W_{C}(a)}_{a=0}^{∞} Algorithm Now that we know that B_{c} is ultimately-periodic, or finite, and hence is uniquely determined by finite data (the non-periodic beginning, and the periodic part), we can treat it as a single concrete computational object rather then as an infinite sequence.

It turns out that W_{c} is not that different than W_{c−1}, hence it would be desirable to find a recurrence scheme that takes advantage of previously computed values. Let’s write

W′_{C}(a) := ⋃_{c=0}^{C−1} V′_{C,c}(a) ,

W′′_{C}(a) := ⋃_{c=0}^{C−1} V′′_{C,c}(a) .

Of course, W_{C}(a) = W′_{C}(a) ∪ W′′_{C}(a). Now

W′′_{C}(a) := ⋃_{c=0}^{C−1} V′′_{C,c}(a) = ( ⋃_{c=0}^{C−2} V′′_{C,c}(a)) ∪ V′′_{C,C−1}(a)

= ( ⋃_{c=0}^{C−2}{B_{c}(a + 1 + (C − 1) − c)}) ∪ {B_{C−1}(a + 1)}

= W′′_{C−1}(a + 1) ∪ {B_{C−1}(a + 1)} .

We also have

W′_{C}(a) := ⋃_{c=0}^{C−1} V′_{C,c}(a) = ( ⋃_{c=0}^{C−2} V′_{C,c}(a)) ∪ V′_{C,C−1}(a) =

⋃_{c=0}^{C−2}{B_{c}(0) − ((C − 1) − c) − a − 1} ∪ {B_{C−1}(0) − 1 − a} =

OneLess(W′_{C−1}(a)) ∪ {B_{C−1}(0) − 1 − a} ,

where OneLess(S) := {s − 1 ; s ∈ S}. In the above we make the convention that negative numbers are discarded. The Recurrence Scheme Now let’s define three macros on ultimately-periodic sequences of sets. The first one is Losers that inputs an ultimately-periodic sequence of sets and outputs an ultimatelyperiodic, or finite, sequence of integers, by employing (F undamentalRecurrence). The second one is OneLess defined by OneLess(A)_{i} := OneLess(A_{i}). Of course it preserves the ultimate-periodicity property. The third macro is Chop that is just a left-shift, discarding the first member. Chop(A)_{i} = A_{i+1}.

Using these three macros, we can rephrase the above scheme without any mention of the argument a, and just treat B_{c}, W′_{c}, and W′′_{c} as objects on their own right. The union of two sequences of sets is defined as the sequence of unions: (S ∪ T)_{i} := S_{i} ∪ T_{i}.

Initial Conditions: W′_{0} = {0}∅^{∞}, W′′_{0} = ∅^{∞}.

Recurrence: For c ≥ 0

B_{c} = Losers(W′_{c} ∪ W′′_{c}) ,
W′_{c+1} = OneLess(W′_{c}) ∪ [{B_{c}(0) − 1}, {B_{c}(0) − 2}, …, {0}][∅]^{∞} ,
W′′_{c+1} = Chop(W′′_{c}) ∪ Chop(B_{c}) .

The Maple package BYRNES

Everything here is implemented in the Maple package BYRNES available from the author’s website. It may be downloaded from

http://www.math.rutgers.edu/~zeilberg/mamarim/ mamarimhtml/byrnes.html ,

where you can also find a data file called ChompData, and detailed instructions.

The main procedures are ChompLosers and ChompGrudny .

The Sprague-Grundy Values

Losing positions are those for which the Sprague-Grundy function (nim-value) equals 0. The above can be repeated, with little modification, to compute the set of positions that have any given nimvalue. The only difference is that for any given g, one has to add to the set of implied “Instant Winners”, the positions that have been already shown to have smaller nim-values. It follows by induction on g that these too yield ultimately-periodic sequences. This is implemented in procedure ChompGrundy in BYRNES. Read the on-line help there.

Chaotic Behavior

As first noted by Brouwer[Br] for the losing positions, and Sun[S] for the values of the nim-values, larger periods then 1 do occur, and while at the beginning they are rather rare, eventually they take over, and the periods get rather large. Also the set of c for which B_{c} is a finite sequence (i.e. it ends with a 0) is rather mysterious. It seems that we have ‘chaotic’ behavior, but in a vague, yet-to-be-made-precise, sense.

Conclusion: Chomp is Locally Trivial But NOT Globally Trivial

What Xinyu Sun conjectured, Byrnes proved, and I reproved is that 3-Rowed Chomp is locally trivial, since for every fixed number of squares at the bottom row, c, the sequence coding the set of losing positions, B_{c}, is ultimately-periodic or finite.

But it seems that as a function of c, B_{c} is far from trivial. But then again, maybe it conforms to yet-another-ansatz, perhaps reminiscent of Wythoff’s game (see [F]), but probably much more complicated. REFERENCES

[BCG] E. R. Berlekamp, J. H. Conway, and R. K. Guy, “Winning Ways for Your Mathematical Plays”, Academic Press, London, 1982.

[Br] A. Brouwer, Chomp, on-line document, http://www.win.tue.nl/~aeb/games/chomp.html .

[By] S. Byrnes, Poset Games Periodicity, preprint.

Available from: http://www.geocities.com/sbyrnes321/pgp.html .

[E1] S. Elaydi, “An Introduction to Difference Equations”, 2nd edition, Springer Verlag, 1999.

[E2] S. Elaydi, “Discrete Chaos”, CRC Press, 1999.

[F] A. S. Fraenkel, Scenic Trails Ascending from Sea-Level Nim to Alpine Chess, in: “Games of No Chance”, R. J. Nowakowski, ed., Cambridge University Press, 1996.

[G] D. Gale, A Curious Nim-type game, Amer. Math. Monthly 81 (1974), 876-879.

[S] X.Sun, Improvements on Chomp, Integers 2 (2002), G1, 8 pp. (electronic).

[Z] D. Zeilberger, Three-rowed Chomp, Adv. in Appl. Math.26 (2001), 168–179. Available on-line

from: http://www.math.rutgers.edu/~zeilberg/mamarim/ mamarimhtml/chomp.html .