The game of Chomp

Chomp is a game played on a partially ordered set P with smallest element 0. A move consists of picking an element x of P and removing x and all larger elements from P. Whoever picks 0 loses.

For nice pictures, see David Molnar's page and Helen Joyce's page. An applet.

Existence of a winning strategy

If P has a largest element 1, different from 0, then a trivial strategy-stealing argument shows that the first player wins. (If picking 1 does not win, it is because the opponent has the devastating reply a. But in that case the first player wins by starting with a.)

However, the argument is non-constructive: the winning move is unknown.

Chomp on a simplicial complex

Take for P the lattice 2n of all subsets of an n-set. (This game is also known as "subset takeaway" and as "hyperchomp" and as the "superset game". It is the version of Schuh's game (see below) where N is square-free. It was studied by Gale and Neyman[14].) Since there is a largest element, the first player wins. But how? Gale and Neyman conjecture that taking the top element, the unique n-set, is the winning move, and this is true for n at most 5 (...) and also for n at most 7 (Blokhuis-Brouwer-Doumen).

More generally, Gale and Neyman conjecture that the first player loses on the collection of all subsets of size at most k in an n-set when k+1 divides n, and prove this for k=2.

Chomp on graphs

Take for P the empty set and the vertices and edges of a graph. This situation was studied by Jan Draisma and Sander van Rijnswou [13]. They show that on the complete graph Kn the first player wins if and only if n is not divisible by 3 (reproving Gale and Neyman's result), and settle 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. An applet.

More generally, Tirasan Khandhawit and Lynnelle Ye [16] find for bipartite graphs that the first player loses iff the number of vertices and the number of edges are both even. (They determine the Grundy function of bipartite graphs, and show that it is δ(odd v)+2δ(odd e), where δ(P) = (if P then 1 else 0), and v is the number of vertices, e the number of edges.)

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 one empty set, seven points, seven lines, and one plane.) The proof is by induction on n, using a symmetry argument.

Note that for n at least 1 the winning move is not to take the top element.

History

Fred. Schuh published in 1952 his "game of divisors" ([1]). Here the partially ordered set is that of all divisors of a fixed number N, with x below y when y|x.

David Gale reinvented this game ([2,2a]). His version is that of the m-by-n chocolate bar, where square (0,0) (say, the lower left-hand corner) is poisoned, and players take turns eating a "chomp": a square (a,b) together with all squares to the left and/or above it.

This game corresponds to Schuh's game with N = pm-1 . qn-1 for two primes p, q.

The name Chomp was invented by Martin Gardner [3].

The game is also mentioned in Halmos' problem book [10], with a very elementary discussion.

Doron Zeilberger [4] analysed the special case of a 3-by-n chocolate bar, and wrote a program that could give the complete solution for 3-rowed chocolate bars with lengths p, q, r (p not less than q and q not less than r) for r at most 115. He finds very simple patterns, but very soon after the 115 things get more complicated as we shall see below.

Xinyu Sun ([5]) extends Zeilberger's results to Chomp with more than three rows (and he remarks explicitly that 3-rowed Chomp seems to have simple linear patterns).

Trivial cases

m-by-m Chomp (with m at least 2) is easy: just start by picking the square (1,1), and after that answer by symmetry. Also 2-by-m Chomp is easy: the P-positions (the positions in which the Previous Player wins, that is, the player to move loses) are (a+1,a): those with two rows of lengths differing by one. In both cases the winning move is unique. These cases were already given in Schuh [1] and Gale [2].

Is the winning move unique?

David Gale reports that the winning move in 3-by-n Chomp is unique for n at most 100 and also in 2-by-n, n-by-n, 4-by-5 and 4-by-6 Chomp.

Martin Gardner [3] 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-by-10 Chomp. (See also [9], p. 598.) On the other hand, explicit computation shows that the winning move is unique in 3-by-n Chomp for n at most 130000, see below.

Money

David Gale offers $100 (see [7]) for a complete analysis of finite 3D Chomp. (Of course, today we are not even able to analyse 2D, that is, m-by-n Chomp.)

Let N be the set of natural numbers. David Gale offers $200 (see [8]) for the answer to the question whether N3 (with natural partial order, "3D Chomp") is a first-player win. This is an infinite poset, but every game ends after finitely many moves. More generally, games will have finite length when the poset P does not have infinite antichains, and does not have infinite descending chains.

Of course N2 is easily won: the first player picks (1,1) and answers (a,0) by (0,a) and vice versa. Transfinite Chomp is studied by Scott Huddleston and Jerry Shurman [6].

3-by-n Chomp

In 3-by-n Chomp a game position is (p,q,r) with p not less than q and q not less than r.

If r = 0 then this is really 2-by-n Chomp, and the P-positions (previous player wins) 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 nonnegative a.

This is the general pattern for small r: either there are finitely many P-positions (*,*,r), because (p,p,r) occurs, or there are infinitely many, and in that case after an initial amount of junk there is a linear pattern, where p and q differ by a constant.

The first exception is r = 120, where the values of p as a function of q for q at least 120 are: 206 205 207 208 203 209 210 199 211 212 213 198 214 215 195 217 216 194 219 220 221 222 190 188 218 223 224 225 186 227 226 228 229 230 180 231 184 233 232 234 178 236 235 237 174 175 238 240 239 172 242 241 244 243 246 245 248 247 250 249 252 251 254 253 256 255 258 257 260 259 262 261 264 263 266 265 268 267 270 269 272 271 274 273 276 275 278 277 280 279 282 281 284 283 286 285 288 287 290 289 292 291 294 293 296 295 298 297 300 299 302 301 304 303 306 305 308 307 310 309 312 311 314 313 316 315 318 317 320 319 322 321 324 323 326 325 ... That is, after an initial amount of junk ending in (172,169,120) we get a pattern a a-1 a+2 a+1 a+4 a+3 a+6 a+5 ..., that is, p = q + constant + (-1)q.

Later more complicated patterns occur, see below.

Recurrence

Let f(q,r) be the unique p such that (p,q,r) is a P-position. (Here (p,q,r) stands for (p,min(p,q),min(p,q,r)).) There is a simple recurrence for f(q,r):

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.

A small table

The table below gives the value of f(q,r) for small q and r with r not larger than q. Here q varies horizontally, from 0 to 24, and r varies vertically, also from 0 to 24.

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 23 23
15|                                            27 26 28 29 30 23 31 22 22 22
14|                                         25 26 23 27 28 22 29 30 31 32 33
13|                                      24 23 22 25 26 27 19 19 19 19 19 19
12|                                   21 23 22 24 19 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 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 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  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  7  7  7  7  7  7  7  7  7  7  7  7  7  7  7  7  7  7
 3|         6  7  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  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
----------------------------------------------------------------------------
q: 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

The algorithm given is fairly efficient, and can still be improved a little, so that it is not difficult to compute f(q,r) for moderately large values of q,r. We did a computation with q,r running up to 130000.

Column max on diagonal

Elements on the diagonal are the largest element in their column.

Indeed, suppose f(q,q) is not the largest in column q, but f(q,r) with r < q is the largest. Then why is none of the numbers f(q,s) (r+1 <= s <= q) at the position (q,r)?

The column (q,*) contains q+1 different numbers f(q,r), all of them positive integers, 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 <= r since above the diagonal verticals are constant. So, they all occur at (t,r) with r+1 <= t <= q-1. But there are more numbers s than positions t, contradiction.

So, indeed, f(q,q) is the largest in its column.

P-positions (q,q,r)

We show that for each p there are at least p/3 P-positions (q,q,r) with q < p.

Indeed, it suffices to show this for p = 3n. Suppose not, so that there are fewer than n P-positions (q,q,r) with q <= 3n-1. Pick m = 2n-1. Among the m+1 values f(m,r) there are fewer than n that are at most m, so f(m,m) >= 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 of these values q occur in P-positions (q,q,r), so at least 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) > u) and fewer than n values f(u,r) are at most u, so f(u,u) > 2u+1-n > 3n. But f(u,u) < 3n by definition. Contradiction.

Patterns in 3-by-n Chomp

As mentioned above, in row r = 120 we see for the first time a pattern that is not just a constant function f(q,r) = c or a linear function f(q,r) = d+q. We see a repeating pattern 1 -1 1 -1 .. (of period 2) superimposed on the linear function. Observed patterns for small r (table with corrections from Gabriel Nivasch)
r	start	period	pattern
120	170	2	1 -1
400	566	2	1 -1
402     571     4       0 1 1 -2
422     597     2       1 -1
424     600     4       0 1 1 -2
513     725     2       -1 1
576     814     2       -1 1
583     824     2       1 -1
585     828     4       1 1 -2 0
593     838     2       -1 1
605     856     2       1 -1
610     863     2       1 -1
861     1217    2       1 -1
888     1255    2       1 -1
890     1258    4       0 1 1 -2
892     1265    4       0 0 1 -1
904     1278    2       1 -1
...
2027    2867    3       1 1 -2
...
6541    9250    9       1 1 1 -3 0 1 1 1 -3
Gabriel Nivasch wrote (and I agree):
Here's what I find up to r = 10000:

Period 2 for r = 120, 400, 422, 513, 576, 583, 593, 605, 610, 861, 888,
904, 1013, 1059, 1129, 1141, 1163, 1216, 1281, 1291, 1419, 1448, 1508,
1523, 1537, 1561, 1723, 1747, 1824, 1868, 1875, 1889, 2003, 2010, 2172,
2213, 2256, 2423, 2517, 2642, 2778, 2882, 2896, 2932, 2969, 3152, 3157,
3222, 3256, 3355, 3369, 3454, 3495, 3531, 3818, 4009, 4173, 4178, 4202,
4289, 4345, 4509, 4596, 4690, 4770, 4787, 4883, 4912, 4934, 5086, 5168,
5231, 5349, 5390, 5455, 5562, 5595, 5610, 5663, 5673, 5694, 5757, 5762,
5839, 5851, 5885, 5996, 6071, 6095, 6107, 6141, 6230, 6240, 6252, 6276,
6351, 6392, 6462, 6467, 6498, 6684, 6711, 6824, 6882, 6964, 6974, 7041,
7230, 7365, 7377, 7394, 7430, 7498, 7633, 7660, 7669, 7710, 7739, 7802,
7850, 7879, 7976, 8111, 8147, 8152, 8246, 8519, 8560, 8835, 8893, 9004,
9067, 9084, 9149, 9178, 9241, 9552, 9760, 9767, 9784, 9888.

Period 3 for r = 2027, 2751, 6539, 6746, 7693, 7961, 8765.

Period 4 for r = 402, 424, 585, 890, 892, 1015, 1143, 1293, 1295, 1525,
1870, 2012, 2780, 2782, 2884, 3371, 4204, 4291, 4347, 4511, 4513, 4598,
4692, 4694, 4772, 4774, 4914, 5088, 5392, 5597, 5764, 5841, 5853, 5887,
5889, 6073, 6109, 6394, 6686, 6976, 7232, 7396, 7500, 7502, 7662, 7664,
7671, 7804, 7881, 7978, 9086, 9151, 9243, 9245.

Period 9 for r = 6541, 8767.

Byrnes' theorem

Steven Byrnes [11] proved that the above observations hold in general, i.e., that for fixed r the value of p-q for P-positions (p,q,r) will be eventually periodic. (This earned him a $100000 scholarship.)

A nice exposition of the proof was given by Zeilberger [12].

Sequences from 3-by-n Chomp

(i) Values of p where there is a P-position (p,q,q), with terms indexed by q: 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, ... (more terms)... This is sequence A029900 in Sloane's Encyclopedia of Integer Sequences. Note that it is not monotonic; e.g. 89 is followed by 88. However, in the first 130000 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 a = 1 + (1/2)sqrt(2) (about 1.7). It looks like this sequence grows like an, and stays within a strip of width 3.5 around this. (For n below 130000 the n-th term lies between an-1.310 and an+2.141.)

(ii) Values of p for which there is a P-position (p,p,r): 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, 123, 126, 127, 131, 132, 135, 137, 140, 142, 145, 147, 149, ... (more terms)... This is sequence A029901 in EIS. (Below 130000 we find 53847 terms. Differences between successive terms are 1, 2, 3, 4 or 5 with frequencies 0.117, 0.429, 0.376, 0.078, 0.00006.) Let b = 1 + sqrt(2) (about 2.4). It looks like this sequence grows like bn, and stays within a strip of width 3 around this. (For n below 53847 the n-th term lies between bn-1.506 and bn+1.493.)

It is conjectured that sequences (i) and (ii) are complementary. In other words, that the winning move in (p,p,p) is unique. Each number below 130000 belongs to precisely one.

(iii) Values of r for which there is a P-position (p,p,r): 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, ... (more terms)... This is sequence A029902 in EIS. It resembles sequence (i) a bit, but is monotonic by definition (and in the first 53847 terms the difference between two successive terms is 1, 2 or 3, with frequencies 0.317, 0.658, 0.024). It looks like this sequence grows like an, and stays within a strip of width 3 around this. (For n below 53847 the n-th term lies between an-1.853 and an+0.940.)

For the remaining values of r, the function f(q,r) grows without bound. Sloane conjectures in sequence A029905 in EIS that in such cases one has f(q,r) = q + const. for large q (if I interpret the very short description correctly), but this is not the case. For example, as we saw, row 120 has f(q,r) - q for large q periodic with period 2. But let us look at the cases where f(q,r) = q + c for large q. Then one has the three sequences: (a) the r for which this happens, (b) the c one finds, (c) the q0 past which this holds. These sequences are:

(a) 0, 2, 5, 7, 9, 11, 14, 17, 19, 22, 24, 26, 28, 31, 34, 36, 38, 40, 42, 45, 48, 51, 53, 56, 58, 60, 62, 65, 67, 69, 72, 74, 77, 79, 82, 84, 86, 88, 91, 95, 97, 99, 101, 104, 106, 108, 110, 112, 115, 119, 124, 126, 128, 130, ... This is sequence A029905. (And there is no term 120.)

(b) 1, 2, 4, 5, 6, 7, 9, 11, 12, 14, 15, 16, 17, 19, 21, 22, 23, 24, 25, 27, 29, 31, 32, 34, 35, 36, 37, 39, 40, 41, 43, 44, 46, 47, 49, 50, 51, 52, 54, 56, 58, 59, 60, 62, 63, 64, 65, 66, 68, 71, 74, 75, 76, 77, ... This is sequence A029903.

(c) 0, 2, 7, 10, 12, 19, 20, 24, 27, 31, 34, 36, 39, 44, 48, 50, 56, 60, 63, 63, 67, 73, 75, 79, 82, 84, 88, 92, 95, 97, 101, 104, 108, 112, 117, 121, 121, 125, 129, 133, 138, 140, 143, 147, 150, 152, 155, 158, 162, 169, 176, 178, 182, 184, ... This is sequence A029904.

Finally, sequence A029899 gives the number of P-positions (p,q,r) with 0 <= r <= q <= p <= n.

Sloane refers to Fred Lunnon (fred@cs.may.ie) for the first few terms of these sequences.

(iv) The Grundy values of 3-by-n Chomp as a function of n are given by sequence A069001 in EIS: 2, 4, 5, 9, 11, 12, 13, 16, 19, 21, 24, 26, 28, 31, 32, 35, 36, 39, 42, 41, 44, 46, 50, 52, 55, 56, 59, 62, 61, 64, 67, 69, 73, 74, 76, 78, 80, 83, 84, 85, 87, 89, 93, 94, 96, 97, 100, 101, 106, 107, 110, 113, 112, 114, 118, 121, 120, 124, 127, 129, 132, 131, 136, 138, ...

Sloane refers to Michael Zahniser (zahniser@stolaf.edu) for the first few terms of these sequences.

Renormalization

Friedman and Landsberg show in [15] that if one assumes that for given r the P-positions [p,q,r] are distributed along three lines in the p-q plane, and that for different r one obtains the same picture after scaling, then the equations of these lines are determined. In particular, they derive the above constants (like a = 1 + (1/2)sqrt(2)) from their assumptions.

2-by-2-by-n Chomp

In more dimensions things get more difficult. However, 2-by-2-by-n Chomp is still easy. The winning move is to take the top. P-positions are: (p,p,p,p-1), (p,a,b,c) with a+b=p-1 and c=min(a,b).

References

[1] Fred. Schuh, Spel van delers, Nieuw Tijdschrift voor Wiskunde 39 (1952) 299-304.

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

[2a] D. Gale, A curious Nim-type game, Appendix 1 in: Tracking the Automatic Ant, Springer, New York, 1998. ISBN: 0-387-98272-8.

[3] Martin Gardner, Mathematical Games, Scientific American, Jan. 1973, pp. 110-111. (Also, May 1973.)

[4] Doron Zeilberger, Three-Rowed CHOMP, Adv. Applied Math. 26 (2001) 168-179.

[5] Xinyu Sun, Improvements on Chomp.

[6] S. Huddleston and J. Shurman, 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.

[6a] talk.

[7] p. 482 in: Games of No Chance (R. J. Nowakowski, ed.), Cambridge University Press, 1998.

[8] David Gale, Mathematical Entertainments, The Mathematical Intelligencer, Vol. 15 No. 3 (Summer 1993), pp. 59-60, and Vol. 18 No. 3 (Summer 1996), p. 26.

[9] Elwyn R. Berlekamp, John H. Conway and Richard K. Guy, Winning Ways, Academic Press, London, 1982, pp. 598-601.

[10] Paul Halmos, Problems for Mathematicians, Young and Old, Dolciani Math. Expositions Nr. 12, Math. Assoc. America, 1991. ISBN: 0-88385-320-5. pp 43-46 and 212-215 are about chomp.

[11] Steven Byrnes, Poset game periodicity, Electr. J. Combin. Number Th. 3 (2003).

[12] Doron Zeilberger, Chomp, recurrences, and Chaos(?), 2003. PS

[13] Jan Draisma and Sander van Rijnswou, How to chomp forests, and some other graphs, 2002. PDF

[14] D. Gale and A. Neyman, Nim-type games, Internat. J. Game Theory 11 (1982) 17-20.

[15] Eric J. Friedman and Adam Scott Landsberg, Scaling, Renormalization and Universality in Combinatorial Games: the Geometry of Chomp, preprint, March 2005.

[16] Tirasan Khandhawit and Lynnelle Ye, Chomp on graphs and subsets, preprint, 2011.