Three-Rowed CHOMP

Doron ZEILBERGER ^{1}

Abstract: A “meta” (pseudo-) algorithm is described that, for any fixed k, finds a fast (O(log(a))) algorithm for playing 3-rowed Chomp, starting with the first, second, and third rows of lengths a, b, and c respectively, where c ≤ k, but a and b are arbitrary.

How To Play CHOMP

David Gale’s famous game of Chomp ([Ch]) 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.

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. zeilberg@math.temple.edu

http://www.math.temple.edu/~zeilberg/ . September 5, 2000. Supported in part by the NSF. This article is accompanied by the Maple package Chomp3Rows, available from Zeilberger’s website.

The Two Cultures of Mathematics: Existential and Constructive

Nineteenth century mathematicians were honest. When they tried to prove that something existed, they tried to find it, explicitly. Then came Hilbert along, and turned math into theology by “proving” existence by using the “Law” of the Excluded Middle. Of course, 20th-century mathematicians were forced to cheat, because they ran out of “computing time” and “memory allocation” in their tiny PC between their shoulders.

Now that we have much more powerful silicon brains to aid us, we can afford again the luxury of being honest, and actually finding the desired objects, at least whenever it is theoretically possible.

Of course, in (finite) combinatorics, there is no philosophical objection to using indirect arguments, but it is still much more satisfying to exhibit the object rather than just proving its existence.

One of the most gorgeous existence proofs of all times is the following gem of David Gale ([Ch]).

The Chomp Existence Theorem: In a Chomp game that starts with an M by N chocolate bar (with MN > 1), there exists a winning move for the first player.

David Gale’s One-Line Proof: Consider the minimal move of only removing the square at the bottom-rightmost corner, (M, N). If it is a winning move, then it is a winning move. Otherwise, it is a losing move. But in the latter case, this means that your opponent has a good counter-move. It is immediate that any position reachable from the new position (with MN − 1 squares) is also reachable from the initial position (with MN squares). Hence the first player could have gotten to that position right away.

This famous (but not famous enough!) proof can be used in practice as follows. I first play with Kasparov, pretending that I am Deep Blue, and make the above trial move of removing the bottomright corner. If he resigns, then it is a good move, otherwise, he would make a good counter-move, that I can use when I play with you. This idea is called ‘strategy stealing’ in [WW].

How to Find the Winning Move?

Of course, there exists an algorithm for finding the winning move, and more generally of deciding whether any given Chomp position is winning or losing, and finding a winning move in the former case. This is true for all combinatorial games where the number of possible positions is finite, and the game graph is acyclic. This is part of the lovely theory of combinatorial games. Readers not familiar with this beautiful theory are strongly advised to read Aviezri Fraenkel’s lively and very lucid introduction [ST].

First one “draws” the game graph of the game. This is a directed graph whose vertices are all possible “game positions”, and there is a directed edge between the vertex corresponding to position P_{1} and the vertex corresponding to position P_{2} if P_{2} is reachable from P_{1} in one legal move.

Having ‘drawn’ that graph, you label all the sinks (vertices with outdegree 0) by P (for ‘Previous player wins’), because if it is your turn to move and you are there, then you lost, because you can’t go anywhere. Next label all vertices that have at least one edge leading to a P-vertex, by N (for ”Next player wins”). Then, if you see a vertex all of whose edges lead to N -labelled vertices, label it P. Continue to alternately label the vertices N and P until you finish.

If the directed graph of the game is finite and has no cycles, then it is easy to see that the above procedure always terminates.

Now let’s apply this to Chomp. How many possible positions are there? The intermediate positions in an M ×N Chomp are integer-partitions (non-increasing sequences of positive integers) λ_{1} ≥ λ_{2} ≥ … ≥ λ_{r}, with λ_{1} ≤ N and r ≤ M. It is well known and easy to see that their number is \binom{M+N}{N}. So for example when M = O(N), we have an exponential size graph, and hence an exponential-time and exponential-memory algorithm for labelling it (and doubly-exponential in bit size!).

When M = N, there is a trivial winning move. Choose to chomp at the square at location (2, 2), leaving a symmetric L-shaped shape, and then use the copy-cat strategy of aping your opponent’s move to the other arm of the L-shape.

Another trivial special case is when we only have 2 rows. We have

Proposition 0: A 2-rowed Chomp position is P iff it is of the form (a, a − 1) (a ≥ 1), i.e. where the top row has one more square than the bottom row. If (a, b) (a ≥ b ≥ 0) is a Chomp position that is winning (i.e. b ≠ a − 1), then if a − b ≥ 2, a winning move is to go to position (b + 1, b), and if a − b = 0, to go to position (b, b − 1).

Proof: We really have two statements here:

P_{1}(a): (a, a − 1) is a P position (for all a ≥ 1).

P_{2}(b): (a, b) is an N position for every a such that a ≥ b ≥ 0, and a − b ≠ 1. Furthermore the winning move is (a, a − 1) if a = b and (b + 1, b) if a − b ≥ 2.

The proof is by joint induction. P_{1}(1) is trivially true. The positions reachable from (a, a − 1) are (a − 1, a − 1), and (a, a − 2),(a, a − 3), …, (a, 0), each of which are N positions because of P_{2}(b), for b < a. Hence P_{2}(b) for b < a imply P_{1}(a).

But also P_{2}(b) is implied by P_{1}(b − 1), if a = b, and by P_{1}(b) if a − b = 2.

So we have that P_{1}(b − 1) and P_{1}(b) imply P_{2}(b), and P_{2}(i), i = 1 … b − 1 imply P_{1}(b). Since P_{1}(1) is true, this completes the induction.

What is the Computational Complexity of 2-Rowed Chomp?

First note that when we fix the number of rows and play k × n-Chomp, and only let the number of columns, n, get larger, then the naive algorithm is no longer exponential in n, but rather is O(n^{k}). But in order to represent a position in k-rowed Chomp, we only need O(log n) bits, hence the naive algorithm is still exponential in the size of the input for any fixed number of rows, and hence doubly-exponential for general Chomp.

On the other hand, the algorithm of Prop. 0, for 2-rowed Chomp, is clearly linear in the bit-size of the input, both for deciding whether it is a P or N position, and for finding a winning move in the latter case.

IMPOSSIBLE DREAM: Find a polynomial-time algorithm (in the bit-size of the input) for Chomp.

In particular, such an algorithm would quickly (i.e. in time polynomial in log n and k) find the winning first move in a k×n Chomp, whose existence is guaranteed by Gale’s clever strategy-stealing argument.

Since the above dream is impossible, we have to find more realistic dreams. We should not be like the fictional Uncle Petros from Apostolos Doxiadis’s novel, who ‘wasted’ his life trying to prove the Goldbach Conjecture, and like the real Paul Cohen, who is rumored to have ‘wasted’ the second half of his life trying to prove the Riemann Hypothesis.

So let’s be more modest and try to find a fast algorithm (in log n) for k-rowed Chomp, where k is fixed. Even this is probably impossible. So let’s be even more modest and try to do it for k = 3, granted that we already know how to do it for k = 2. Even this seems to be impossible, at least for me. So what is a poor mathematician to do? The case k = 2 is known and trivial, while the case k = 3 is (probably) impossible. This is just one instance of the human mathematician’s predicament of walking the

TIGHTROPE BETWEEN the TRIVIAL and the IMPOSSIBLE

One may define the cutting edge of research as that x for which doing x − ϵ is utterly trivial while doing x + ϵ is impossible.

It is not unlike designing a math exam for my calculus students. If I give them the kind of tests that I used to take, and even much easier ones, they will all flunk. On the other hand, if I’ll ask them to find 2 + 2, 2 + 3, and problems like that, and allow calculators, most of them will get an A. It is non-trivial to design a test that is of “just right” level of difficulty to produce a bell-shaped curve.

This ‘trivial for k = 2, impossible for k = 3’ curse brings to mind the “Three Body Problem”. One way out of the impossibility dead-end is to abandon the quantitative and go to the qualitative, as did Poincaré. This lead to another cultural divide.

The Two Cultures of Mathematics: Quantitative and Qualitative.

But proving existence, uniqueness, and ergodicity will never get us to the moon, nor will it predict the planetary orbits for the next ten thousand years. For that, mathematicians took advantage of the fact that planets are much lighter than the Sun, and used perturbation expansion, starting with the solution of the 2-body problem. This leads to

The Two Cultures of Mathematics: Exact and Approximate.

The approximate culture gave rise to numerical analysis and its theoretical parent, approximation theory. It is approximate mathematics that is the most useful in the sciences. The whole edifice of Feynman diagrams was designed to find ‘series expansions’ that go from a trivial ϕ^{2} (Gaussian) functional integral to an impossible ϕ^{3}-and-beyond functional integral. Its practical effectiveness and amazing agreement with experiment is due to the lucky coincidence(?) that the fine structure constant is fairly small (roughly 1/137). The default in physics is ‘perturbative’, and whenever a ‘non-perturbative’ answer is found, like in Nati Seiberg’s astounding tour-de-force that lead to the Seiberg-Witten invariants and to much more, it is a cause of celebration in physics (and in this case also in math, because of its far-reaching implications in topology).

Speaking of Quantum Field Theory, most of it is non-rigorous, and this brings to mind another cultural divide, this time involving the broader community of people who use mathematics, as opposed to full-time mathematicians.

The Two Cultures of Doing Mathematics: Rigorous and Non-Rigorous.

According to Pierre Cartier’s charming and fascinating article [Ma] professional mathematicians should pay more attention to the latter, since ([Ma], p.1) “There is another way of doing mathematics, equally successful, and the two methods should supplement each other and not fight”. Yet another way, is to compromise and do semi-rigorous math as I proposed in my celebrated manifesto [SR].

Back to Chomp

But the term ‘approximation’ is not appropriate in this context, since everything is discrete. A position is either P or N. Perturbation is more pertinent. An arbitrary 3-row Chomp position can be described as (a, b, c) where a,b, c are the lengths of the top, middle, and bottom rows respectively, and of course a ≥ b ≥ c ≥ 0. When c = 0, we are back to 2-row Chomp, so the next thing to try is to characterize the P positions when c = 1. Let’s try and do it. We know that (b + 1, b, 1) is N, since chomping the bottom cell (the sole cell of the bottom row), leads to the P position (b+1, b, 0). We also know that (1, 1, 1) is N, since the P position (1, 0, 0) is reachable from it. We also know that (a, 0, 0), for a > 1, is N, since we can get to (1, 0, 0) from it. From the 2-rowed case we know that (a, a, 0), and (a, b, 0) with a − b ≥ 2 are N. What are the ‘smallest’ positions with c ≤ 1, that are P ?. We see that all the four-cell positions: (4, 0, 0), (3, 1, 0), (2, 2, 0), (2, 1, 1) are N. Amongst the five-cell positions: (5, 0, 0), (4, 1, 0) are N, since the former can be answered by (1, 0, 0) and the latter by (2, 1, 0). We already know, from the 2-rowed case, that (3,2,0) is P, and now we see that (2,2,1),(3,1,1) are both P, since all the positions reachable from them are N (do it!).

So, now we have two new members of the P club: (2, 2, 1), and (3, 1, 1). But this two factoids entail an infinite number of new memberships in the N club!, namely (2+α, 2+β, 1) for all α ≥ β ≥ 1, as well as (2 + α, 2, 1) for α ≥ 1. Also, from the fact that (3, 1, 1) is P we get that (3, 2, 1), (3, 3, 1) are N, as well as (3 + α, 1, 1) for α ≥ 1. Now it is easy to see (do it!) that these N positions exhaust all the possible positions with more than 5 cells and c ≤ 1. Hence:

Proposition 1: The only P positions (a, b, c), with c = 1, are (2, 2, 1) and (3, 1, 1). Every N position with c = 1, and at least 6 cells, is (at least) in one of the forms: (3, 2, 1);(3, 3, 1);(4 + α, 1, 1)(α ≥ 0); (2 + α, 2 + β, 1)(α ≥ β ≥ 0, α + β > 0) where (α ≥ β ≥ 0), and the winning moves are, respectively:

(3, 2, 1) → (3, 1, 1) ,
(3, 3, 1) → (3, 1, 1) ,
(4 + α, 1, 1) → (3, 1, 1) ,
(2 + α, 2 + β, 1) → (2, 2, 1) .

Note that there turned out to be only 2 members of P when c = 1, so we did not need induction. On the other hand when c = 0 (the 2-rowed case), there were infinitely many members, so we had to resort to induction.

Now we are ready to graduate to the case c = 2. From the P positions for c = 0 we know that (b + 1, b, 2) all belong to N (you chomp-off the last row), and from (3, 1, 1) ∈ P we know that (3, 2, 2) ∈ N, and from (2, 2, 1) ∈ P we know that (2, 2, 2) ∈ N. Hence the smallest (according to the number of cells) P position is (4, 2, 2), since all the possible moves lead to N positions. Now this fact implies that (4, 3, 2), (4, 4, 2) are N positions. The smallest P position is (5, 3, 2), which immediately implies that (5, 4, 2) ∈ N and (5 + α, 3, 2) ∈ N, for α ≥ 1. The smallest position that is not covered by the above is (6, 4, 2), and we can directly verify that all the possible moves from (6, 4, 2) lead to N positions. So (6, 4, 2) ∈ P. Continuing, we get that also (7, 5, 3) ∈ N, and we humans would be soon lead to conjecture the following

Proposition 2: A Chomp position (a, b, 2) is P iff a − b = 2.

Now this is a genuine proposition, since it contains infinitely many statements: (4, 2, 2) ∈ P, (5, 3, 2) ∈ P, (6, 4, 2) ∈ P, . . .. Nevertheless, we humans can easily prove it by induction like we did prove Proposition 0 for c = 0 (the two-rowed case). Why won’t YOU do it RIGHT NOW?!

We can continue in this vein, but I doubt that any human can go beyond c = 10, since the number of cases grows larger and larger, as we will see below, once we let Shalosh B. Ekhad take over. One hope would be that there would emerge a pattern valid for arbitrary c, that a human would be able to prove by induction or otherwise. However this miracle is probably as unlikely as a closed-form solution to the Three Body Problem. Neither I, nor Shalosh, were able to detect such a pattern, and while Shalosh succeeded, using the Maple package Chomp3Rows, to be described soon, to first conjecture, and then (all by itself!) prove Proposition c_{0}, for c_{0} ≤ 115, characterizing the P positions of the form (a, b, c_{0}), no discernible global pattern emerged (as a function of c_{0}), at least not to us.

So Why is it Interesting?

Gregory Chaitin, standing on the shoulders of Kurt Gödel and Alan Turing, taught us that most results are either undecidable or uncompressible. Whenever there is a pattern, it means that the result is compressible, hence was trivial all-along, we just did not know it. So we humans are destined to only prove trivial results, since any result, once proved, is trivial, for the very reason that we, low-tech humans, were able to prove it. The only way to transcend this triviality predicament, and to be able to prove semi-trivial results, is to ask the computer to help us (see [Op36][Op37]).

In other words, we have this powerful hammer, called the computer, that can hammer so many different nails. Of course, we should not waste our time hammering screws, but when we see a screw, rather than look for a screwdriver, or try to use our mighty hammer to awkwardly hammer it, just leave it alone! There are so many challenging nails around, where our hammer can be used to advantage, that we should keep a lookout for them, and try to nail them, thereby hopefully improving our hammering skills. It would be premature to try and find a computer-proof of the Riemann Hypothesis, so let’s try first to teach the computer how to do research in, say, 3-rowed Chomp. Whenever, we have a class of human theorems where the arguments repeat themselves, it is a good candidate for teaching a computer. So the main justification for developing the package Chomp3Rows was as an étude in computer-generated research. As we’ll get better and better at it, very soon we will be able to tackle the Riemann Hypothesis and other biggies.

I call people like me, ‘mathematical engineers’, and I am sure that this culture of mathematical (software) engineering, will soon be the mainstream one, making the following dichotomy obsolete.

The Two Cultures of Mathematics: Problem Solvers and Theory Builders.

W.T. Gowers [TC], in a fascinating, though somewhat defensive, article, described these two cultures, lamenting that Theory Builders are still the topdogs, and problem-solvers the underdogs. Luckily, this is no longer true! In fact, he himself, a problem-solver by his own avowal, is a living proof of the respectability of problem-solvers, having won the Fields medal.

Since computers are more suited for problem-solving than theory-building (at least for some time to come), I believe that problem-solving will become more and more important. But, with a twist! It would be a total waste of time for a human to solve a problem directly. The mainstream activity of late 21st and 22nd century mathematics would be meta-problem-solving: programming the computer to solve problems, that we humans would never have a chance to prove by ourselves. So Gowers’s two breeds of mathematicians will both die out and give place to the

Mainsteam Culture of Future Mathematics: Programming Computers to do Math.

Back to 3-Rowed Chomp

Since we are restricting attention to 3-rowed Chomp, it is more convenient, at least for the computer, to look at the conjugate partition, i.e. the column-lengths, and write down how many 3’s, how many 2’s, and how many 1’s. So from now on position (a, b, c) will be denoted by [c, b − c, a − b] if c > 0. If c = 0 and b > 0, then it will be denoted by [b, a − b], and if b = c = 0 then we simply write [a]. In order not to confuse these two notations, we will use circular parentheses for the former, and reserve square brackets for the latter. For example (5, 4, 2) is [2, 2, 1] in the new notation, while (4, 1) is [1, 3], and (6) is [6].

In the sequel α and β will denote general non-negative integers. Let’s look at two-rowed Chomp once again. In the new notation the P positions are [α, 1]. These entail that [α, 0] and [α, 2+β] are always N positions, and we call them symbolic winners. We also have the winning-move function f([α, 0]) = [α − 1, 1] and f([α, 2 + β]) = ([α, 1]).

In order to formally prove the above statement, and its analogs for c = 1, 2, …, we could use induction, like we did in the human ramblings above, but we can also prove that the defining property is satisfied. The symbolic winners are disjoint from the symbolic losers (assume, that [α′, 1] = [α, β + 2], then β = −1, a contradiction), and that their union is the set of all possible positions.

Using generating functions, this is equivalent to the formal power series

∑_{[w_{1},w_{2}]∈P} x_{1}^{w_{1}}x_{2}^{w_{2}} + ∑_{[w_{1},w_{2}]∈N} x_{1}^{w_{1}}x_{2}^{w_{2}} − (\frac{1}{(1 − x_{1})(1 − x_{2})} − 1)

having non-negative coefficients. While I don’t have a general algorithm for deciding this for arbitrary formal power series, (and even for arbitrary rational functions, in fact the general problem is undecidable), the simple rational functions that show up in this problem all have their denominator (1 − x)(1 − y) and then one can use Maple’s conversion to partial fractions, and use an obvious necessary condition (and I don’t care whether or not it is sufficient, it worked fine for me) to prove that this is indeed the case.

The reader is urged to study the source-code of the Maple package Chomp3Rows to see how it is done in practice. The novelty is that the computer does ‘general reasoning’ for infinitely many cases by using symbol-crunching rather than mere number-crunching. Another nice thing is that, for any fixed c_{0}, the computer finds, iteratively, the P positions. Every time it finds a new P position it evaluates whether this is it, by checking, using generating functions, that all positions with c ≤ c_{0} are taken care of. If this is not the case, and it has two consecutive P positions [c_{0}, α_{0}, β_{0}] and [c_{0}, α_{0} + 1, β_{0}], it ‘conjectures’ that [c_{0}, α_{0} + α, β_{0}] is a symbolic loser (representing an infinite sequence of P positions), and then tries to prove its conjecture. If it is unable to prove it, it just keeps on going. A priori, we don’t have a (meta-) proof that it would always succeed, so unlike WZ theory, this is only a pseudo-algorithm. But once we succeed, we don’t have to worry about its pseudoness, since once the pudding came out, let’s just enjoy it and eat it, and not worry whether we were justified in trying out the recipe on a priori grounds.

This is the beauty of human research! It is always a gamble. If you know beforehand that your ideas are guaranteed to work out, then it is a routine exercise, not research!

A User’s Manual for the Maple Package Chomp3Rows

As with all my packages, it is available from http://www.math.temple.edu/~zeilberg/. Once you downloaded it (as Chomp3Rows), go into Maple, and type: read Chomp3Rows; and follow the instructions given there. In particular, to get a list of the main procedures, type ezra();, while to get a list of all procedures, type ezra1();. To get help on any particular procedure, type

ezra(ProcedureName); . for example for help with Losers, type ezra(Losers); .

The main procedure is Losers(a,k);. It inputs a symbol, a, and an integer, k, and outputs the set of all symbolic losers [α, β, γ] (in the conjugate notation, i.e. the conjugate partition is 3^{α}2^{β}1^{γ}), such that α ≤ k.

For example, if you type Losers(a,5); you would get: [[[1, 0, 2], [1, 1, 0]], [[2, a,
2]], [[3, 0, 3], [3, 2, 0], [3, 1, 3]], [[4, 0, 4], [4, 1, 4], [4, 3, 0], [4, 2, 4]],
[[5, 0, 5], [5, 1, 3], [5, 2 + a, 4]]].

This means that the only losers when α = 1, are [1, 0, 2] and [1, 1, 0], i.e. (3, 1, 1) and (2, 2, 1); the only losers when α = 2 are those of the form [2, a, 2], (a ≥ 0), or in the usual notation, (4+a, 2+a, 2), etc. My computer, Shalosh B. Ekhad, was able to go as far as k = 115, and in order to save time, this pre-computed table is built-in in the procedure T115.

Using the pre-computed data, encoded in T115(a,k), procedure PTable(k) extends the table given in [WW], p. 599, from k ≤ 26 to k ≤ 115. However, note that [WW]’s table is really implicitly symbolic, even though its authors may not have been aware of it, and it looks numeric. It turns out that whenever the i^{th} column ends with a 0, it means that there are only finitely many losers with γ = i, but whenever it does not end with a 0, it always happens to end with a repeated integer. In reality, as rigorously shown by Chomp3Rows, these two repeated last entries really repeat ad-infinitum, implying a symbolic loser. In addition Ptable(115); extends this all the way to γ ≤ 115.

But in order to play Chomp effectively, it is not enough just to know what the losing positions are. One should also know what is a winning move if you are lucky to be at an N position. This information is furnished by typing WINNERS(a,b,k);. Here a and b are symbols (letters), and k is a positive integer. This will return a table U, where U is the set of symbolic winners, arranged in the form of pairs [winner,loser], where winner is a symbolic winner, and loser is the “winning move” to

be performed. For example, typing op(WINNERS(a,b,1)); yields table([ 1 = {[[1, 1, 1], [1,
0, 2]], [[1, 0, 0], [1]], [[1, a, 1],[a + 1, 1]], [[1, 2, 0], [1, 0, 2]], [[1, 0, 3
+ b], [1, 0, 2]], [[1, 2 + a, b], [1, 1, 0]], [[1, 1, b + 1], [1, 1, 0]]} ]), which

means, e.g., (the last term) that [1, 1, b + 1] is a symbolic winner, and the winning move is to make it into [1, 1, 0].

You can also play (3-Rowed) Chomp fast with the computer, by typing PlayChomp(POS);, where POS is the initial position. For example, try PlayChomp([100000,20000,115]); This would be hopeless in a brute-force, numeric program that implements the naive algorithm.

But even if you are a numerical person, and are only interested in, say, a table of all losers in a 3×115 game of Chomp, then, finding and storing the losers and winners symbolically is much more efficient than listing explicitly all \binom{118}{3} = 266916 cases. If you are also willing to start with nonrectangular positions, with arbitrarily large top two rows, for example (10000000, 1000000, 115), then the numeric program would be hopeless. Very often, clever symbolic computations can save lots of numerical efforts. Conversely, symbolic computation can learn a lot from numerics in efficiency and speed. Hence, another challenge for the future would be to bring together the Two Cultures of Computation: Numeric and Symbolic.

Future Work

It would be worthwhile to extend Chomp3Rows to k-row Chomp, where the lengths of the last k − 2 rows are fixed, but the top two rows are arbitrary. Another interesting problem is to find, automatically, the more refined Sprague-Grundy function, rather than just P-N status. Finally, it is hoped that the present methodology might extend to ‘perturbation expansions’ of Wythoff’s game (a.k.a. Fibonacci-Nim) and other combinatorial games.

References

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

[Ma] P. Cartier, Mathemagics (A tribute to L. Euler and R. Feynman) , preprint.

[Op36] D. Zeilberger, Opinion 36 of Doron Zeilberger: Don’t ask what can the computer do for Me?,

but rather: What Can I do for the Computer?, http://www.math.temple.edu/~zeilberg/Opinion36.html.

[Op37] D. Zeilberger, Opinion 37 of Doron Zeilberger: Programming Computers to Do Math is at

least as much fun as Proving Theorems, http://www.math.temple.edu/~zeilberg/Opinion37.html.

[SR] D. Zeilberger, Theorems for a price: Tomorrow’s semi-rigorous mathematical culture, Notices of the Amer. Math. Soc. 40 # 8, 978-981 (Oct. 1993). Reprinted: Math. Intell. 16 no. 4, 11-14 (Fall 1994).

[ST] 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.

[TC] W. T. Gowers, The Two Cultures of Mathematics, in: “Mathematics: Frontiers and Perspectives”, edited by V. Arnold et. al., Amer. Math. Soc., Providence, 2000.

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