For nice pictures, see David Molnar's page and Helen Joyce's page. An applet.
However, the argument is non-constructive: the winning move is unknown.
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 if and only if k+1 divides n, and prove this for k=2.
However, the Gale-Neyman conjectures are false. For n=7 the first player loses on the collection of all subsets of size at most 3, but wins on the collection of all subsets of size at most 6 (by taking a 4-set) (Brouwer and Christensen[18]).
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.)
Note that for n at least 1 the winning move is not to take the top element.
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).
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.
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].
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.
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.
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.
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.
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.
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 -3Gabriel 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.
A nice exposition of the proof was given by Zeilberger [12].
(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.
[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, arXiv:1101.2718, 2011.
[17] J. Daniel Christensen and Mark Tilford, David Gale's subset take-away game, Amer. Math. Monthly 104 (1997) 762-766.
[18] Andries E. Brouwer and J. Daniel Christensen, Counterexamples to Conjectures About Subset Takeaway and Counting Linear Extensions of a Boolean Lattice, Order (2017).
[19] Ignacio García-Marco and Kolja Knauer, Chomp on numerical semigroups, arXiv:1705.11034, 2017.
[20] Cormac O'Sullivan, A vertex and edge deletion game on graphs, arXiv:1709.01354, 2017.