INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #G07

ON THREE-ROWED CHOMP

Andries E. Brouwer

Department of Mathematics, Technical University Eindhoven, P.O. Box 513, 5600MB Eindhoven, Netherlands

                           Andries.Brouwer@cwi.nl

Gábor Horváth

Department of Algebra and Number Theory, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117

Budapest, Hungary

                            ghorvath@cs.elte.hu

Ildikó Molnár-Sáska

                            msi@ludens.elte.hu

Csaba Szabó^{1}

Department of Algebra and Number Theory, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary

                             csaba@cs.elte.hu

Received: 6/3/03, Revised: 9/20/05, Accepted: 10/16/05, Published: 11/17/05

Abstract

Chomp is a 50 year-old game played on a partially ordered set P. It has been in the center of interest of several mathematicians since then. Even when P is simply a 3 × n lattice, we have almost no information about the winning strategy. In this paper we present a new approach and a cubic algorithm for computing the winning positions for this case. We also prove that from the initial positions there are infinitely many winning moves in the third row.

1. The game of Chomp

Chomp is a game played on a partially ordered set P. A move consists of picking an element x ∈ P and removing x and all larger elements from P. If you cannot move, you lose.

1The research of the last 3 authors was supported by the Hungarian National Foundation for Scientific Research, Grants T043671 and T038059.

An equivalent formulation considers the game Chomp_{o} played on a partially ordered set P_{0} with smallest element 0. A move consists of picking an element x ∈ P_{0} and removing x and all larger elements. If you pick 0, you lose.

We shall require P to be such that no infinite games are possible. That is, P must not have infinite antichains, and must not have infinite descending chains.

In Chomp, if P has a smallest element 0, then I take it, and you lose. If P has a largest element 1 then the first player wins, although he may not know how. Indeed, if picking 1 is a winning move, then there is a winning move. And if picking 1 is refuted by the winning reply x, then the first player starts with x and wins.

When talking about winning or lost positions it is necessary to specify for whom these positions are won or lost. A P-position is a previous player win, that is, the player to move is losing, while an N-position is a next player win. For example, in Chomp the empty poset is a P-position.

This game has been studied for various partially ordered sets P. In Sections 2 through 7 we briefly mention some previous work for certain choices of P. In Section 8 we present a new approach and results in the case of a 3 × n lattice. If we are sloppy in the distinction of Chomp and Chomp_{o}, it will be clear which is meant: if the poset has a smallest element and the game is supposed to last longer than one move, then we are playing Chomp_{o}.

2. Chomp on the Boolean lattice

Consider the lattice of all nonempty subsets of an n-set. It is conjectured (and was proved for n ≤ 7 by Blokhuis, Brouwer & Doumen) that picking the top element is the winning move. More generally, Gale and Neyman [7] conjecture that the first player loses on the collection of all nonempty subsets of size at most k in an n-set iff k + 1 divides n. They proved this for k = 2. The smallest open case is n = 7, k = 3.

3. Chomp on graphs

Take for P the vertices and edges of a graph. This situation was studied by Jan Draisma and Sander van Rijnswou [4]. They show that on the complete graph K_{n} the first player loses if and only if n is divisible by 3 (reproving Gale and Neyman’s result) and settled the case of forests by showing that the first player loses iff the number of vertices and the number of connected components are both even. It follows that all circuits are lost.

4. Chomp on Platonic solids

Take for P the vertices and edges and faces and body of a Platonic solid. What is the winning move? For the tetrahedron, take a vertex to leave the opponent with a K_{3}. For the other four, take the top element (the solid) and play symmetric w.r.t. the center afterwards.

5. Chomp on a projective geometry

An example of a family of partially ordered sets with largest element where one can indicate the winning move (and a winning strategy) is that of subspaces of P G(n, 2), the n-dimensional projective geometry over the field with 2 elements. A winning move is to take a point. (Try this on the Fano plane, with seven points, seven lines, and one plane.) The proof is by induction on n, using a symmetry argument. Note that for n ≥ 1 the winning move here is not the top element.

6. Chomp on a direct product of chains

Probably the first version of this game was given by Schuh [10]. He formulated Chomp_{o} on the lattice of divisors of a given number N. Of course, if N = ∏ p^{e(p)} then this lattice is the direct product of chains of length e(p) + 1. For example, for N = 120 we obtain the game 2 × 2 × 4 Chomp. And for square-free N we obtain Chomp on the boolean lattice.

It is easy to describe the strategy for 2 × 2 × n Chomp. The winning move is to take the top. Let us describe a position by a quadruple [x_{00}, x_{01}, x_{10}, x_{11}], where (i, j, x_{ij}) is the largest element in (i, j, ∗) for 0 ≤ i, j ≤ 1. Now the P-positions are: [m, m, m, m − 1], [m, a, b, c] with a + b = m − 1 and c = min(a, b) and 1 ≤ m ≤ n.

Chomp on a direct product of ordinals was studied by Scott Huddleston and Jerry Shurman [9]. They find for example that 2 × ω and 3 × ω^{ω} and 2 × 2 × ω^{3} and 2 × 2 × ω × ω are P-positions.

It is easy to see that N × N (that is, ω × ω) is a first player win. It is unknown whether N × N × N is a first player win.

7. Chomp on a chocolate bar

The game was reinvented by David Gale [5,6], who described Chomp_{o} on an m×n chocolate bar, that is, on the direct product of two chains. That we have Chomp_{o} and not Chomp is expressed by the fact that the lower left hand corner square (0,0) of the chocolate bar is poisonous. The game was baptised by Martin Gardner [8].

Chomp on a 2 × n bar is trivial - it is a subgame of the 2 × 2 × n game solved above - P-positions are [m, m − 1].

Chomp on a n × n square is also trivial. The first player wins: she takes (1,1), and afterwards answers symmetrically. (And the same strategy works on the infinite poset N × N.)

Chomp on a 3 × n bar is highly nontrivial, and we will spend most of the rest of this note discussing it.

7.1 Is the winning move unique?

David Gale reports that there is a unique winning move in the initial position of 3×n Chomp for n ≤ 100 and also in 2 × n, n × n, 4 × 5 and 4 × 6 Chomp.

Martin Gardner [8] 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 × 10 Chomp. (See also [1], p. 598.) On the other hand, explicit computation shows that the winning move is unique in 3 × n Chomp for n ≤ 100000.

A small Chomp position with more than one winning move is the three-rowed Chomp position [3, 2, 1] (see below) from which one can move to either [3, 1, 1] or [2, 2, 1] and win.

7.2 When should one take the top?

For 2 × n Chomp, the unique winning move is taking the top element. Gale conjectures that for m × n Chomp, with n ≥ m ≥ 3, taking the top element always loses.

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #G07 5

8. Three-rowed Chomp

Consider 3 × n Chomp. During the play, game positions can be given by [p, q, r] where p ≥ q ≥ r.

If r = 0 then this is really 2 × n Chomp, and the P-positions are those with p = q + 1. If r = 1, the only P-positions are [3,1,1] and [2,2,1]. If r = 2, the P-positions are those with p = q + 2. If r = 3, the P-positions are [6,3,3], [7,4,3] and [5,5,3]. If r = 4, the P-positions are [8,4,4], [9,5,4], [10,6,4] and [7,7,4]. If r = 5, the P-positions are [10,5,5], [9,6,5] and [a + 11, a + 7, 5] for a ≥ 0.

8.1 Recurrence relation

For given q, r there is a unique p = f(q, r) such that [p, min(p, q), min(p, q, r)] is a P-position. Indeed, since for given q, r there is at most one P-position [p, q, r] and there are infinitely many possible p, it follows that for sufficiently large x, the position [x, q, r] is an N-position with winning move in the first row, reducing x to p and [x, q, r] to [p, min(p, q), min(p, q, r)].

Let us give a small table of f(q, r) (with q horizontally, and r vertically).

The value of f(q, r) is the smallest positive integer p such that there is no move from [p, q, r] to a P-position [p′, q′, r′]. This gives a simple recurrence:

If r > q, then f(q, r) = f(q, q). (That is, f is constant on verticals above the diagonal.) Otherwise, if f(q − 1, r) < q, then f(q, r) = f(q − 1, r). (That is, if f(q, r) = q then f remains constant on the rest of this row.) If neither case occurs, then f(q, r) is the smallest positive integer not among f(a, r) for a < q or among f(q, b) for b < r.

We see that 1 ≤ f(q, r) ≤ q + r + 1.

This gives a cubic algorithm for computing f(m, m). We computed f(q, r) for q, r ≤ 100000.

8.2 Periodicity

For r = 0, 2, 5 we see for P-positions [p, q, r] that the sequence p − q (indexed by q) is eventually periodic with period 1. For r = 120 it is eventually periodic with period 2. Later

INTEGERS: ELECTRONIC JOURNAL OF COMBINATORIAL NUMBER THEORY 5 (2005), #G07 6

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
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

Figure 1: Table of f(q, r)

one finds larger periods, like period 25 for r = 782 and period 720 for r = 7751.

122 240 241 242 178 243 244 245 175 246 174 174 174 174 174 174 174
121 178 240 175 241 242 243 174 172 172 172 172 172 172 172 172 172
120 175 238 240 239 172 242 241 244 243 246 245 248 247 250 249 252
119 237 174 239 238 240 241 242 243 244 245 246 247 248 249 250 251
118 236 237 238 168 168 168 168 168 168 168 168 168 168 168 168 168
117 168 166 166 166 166 166 166 166 166 166 166 166 166 166 166 166
116 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164 164
115 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248
114 162 162 162 162 162 162 162 162 162 162 162 162 162 162 162 162
165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180

Figure 2: Row 120 becomes periodic with period 2

This is the general pattern: for fixed r, the set of P-positions in row r becomes periodic after a finite amount of initial “‘junk.” This beautiful periodicity theorem was proved by Steven Byrnes [3].

8.3 Diagonal elements are largest in their column

Suppose f(q, q) is not the largest number occurring in column q of the table, but f(q, r) with r < q is the largest. Then why are none of the numbers f(q, s) (r + 1 ≤ s ≤ q) at the position (q, r)?

Column q contains q + 1 distinct positive integers f(q, r), so f(q, r) > q. It follows that f(q, r) is the smallest element that does not occur earlier in the same row or column. Since the numbers f(q, s) are not at the (q, r) position, it follows that they all occur earlier in row r, but not at (t, r) with t ≤ 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, a contradiction.

So, f(q, q) is the largest value in its column. In particular, f(q, q) > q.

8.4 The diagonal sequence

Consider the sequence (d_{n})_{n} where d_{n} = f(n, n) for n ≥ 0. We find 1, 3, 4, 6, 8, 10, 11, 13, 15, 16, 18, 20, 21, 24, 25, 27, 28, 30, 32, 34, 35, 37, 39, 40, 42, 44, 45, 48, 49, 51, 53, 54, 56, 57, 59, 60, 63, 64, 66, 68, 70, 72, 73, 74, 76, 78, 80, 82, 83, 85, 87, 89, 88, 92, 93, 95, 96, 98, 100, 102, 104, 105, 107, 109, 111, 112, 113, 116, 117, 118, 121, ... (For more terms, see [2].)

This sequence is not monotonic (e.g., 89 is followed by 88):

55  95
54  93 94
53  92 91 90
52  88 91 90 92
51  89 86 90 88 91
50  87 88 84 89 86 81
49  85 86 84 87 88 89 79
48  83 84 85 86 81 79 87 88
47  82 81 79 84 83 85 86 77 87
46 80 81 79 82 83 77 75 85 84 86
46 47 48 49 50 51 52 53 54 55

Figure 3: Non-monotonicity of diagonal

However, in the first 100000 terms no decrease larger than 1 occurs (and the difference between two successive terms is −1, 1, 2, 3 or 4, with frequencies 0.015, 0.353, 0.537, 0.085, 0.010). Let α = 1 + 1/\sqrt{2} (about 1.7). It looks like this sequence grows like αn. (For n < 100000 we find αn − 1.242 < d_{n} < αn + 2.141.)

8.5 Existence of constant rows

We’ll call a row constant (or finite) if it is eventually constant. That is, row r is a constant row when for some q we have q = f(q, r), and position (q, r) is called the start and q = f(q, r) is called the value of the constant row. The constant rows are precisely the rows r for which there are only finitely many P-positions [p, q, r].

Every integer that does not occur on the diagonal is the value (and starting q) of a constant row. Indeed, we know that [p, p, p] is an N-position, and a move in the bottom row leads to [p′, p′, p′], still an N-position. So, a winning move is either one in the second row, say to [p, q, q], or in the third row, say to [p, p, r]. In the first case p = f(q, q) occurs on the diagonal, in the second case f(p, r) = p and p is the first coordinate for the starting point of a constant row.

We show that there are infinitely many constant rows. Indeed, choose q such that f(n, n) > f(q, q) for every n > q. Clearly, there are infinitely many choices for q. Then the number p = f(q, q − 1) does not occur on the diagonal (it must differ from f(m, m) for m ≤ q − 1, but we also have f(q, q − 1) < f(q, q) < f(n, n) for n > q) and hence occurs as the value of a constant row.

Slightly more generally, if f(n, n) > f(q, q) for n > q and also for q − m ≤ n < q, then no number f(q, q − i − 1) (0 ≤ i ≤ m) occurs on the diagonal.

Since f(q, q) ≥ q + 1 (because a diagonal element is maximal in its column), a diagonal element is not the start of a constant row.

8.6 The sequence of starting points for constant rows

Consider the pairs (q, r) with f(q, r) = q. The sequence (q_{n})_{n} (with n ≥ 1) of first coordinates of these pairs is 2, 5, 7, 9, 12, 14, 17, 19, 22, 23, 26, 29, 31, 33, 36, 38, 41, 43, 46, 47, 50, 52, 55, 58, 61, 62, 65, 67, 69, 71, 75, 77, 79, 81, 84, 86, 90, 91, 94, 97, 99, 101, 103, 106, 108, 110, 114, 115, 119, 120, ...

It is conjectured that for 3 × n Chomp the winning move in the initial position is unique. (And this is true for n < 100000.) If this holds then the two sequences (d_{n})_{n} and (q_{n})_{n} have no elements in common, and one is the complement of the other.

Let β = 1 + \sqrt{2} (about 2.4). It looks like this sequence grows like βn. (For n < 41420 we find βn − 1.506 < q_{n} < βn + 1.493. The differences between successive terms were found to be 1, 2, 3, 4 or 5 with frequencies 0.116, 0.430, 0.376, 0.077, 0.0001.)

The sequence (r_{n})_{n} (with n ≥ 1) of second coordinates of these pairs is 1, 3, 4, 6, 8, 10, 12, 13, 15, 16, 18, 20, 21, 23, 25, 27, 29, 30, 32, 33, 35, 37, 39, 41, 43, 44, 46, 47, 49, 50, 52, 54, 55, 57, 59, 61, 63, 64, 66, 68, 70, 71, 73, 75, 76, 78, 80, 81, 83, 85, 87, 89, 90, 92, 93, 95, 96, 98, 100, 102, 103, 105, 107, 109, 111, 113, 114, ...

It looks like this sequence grows like αn. (For n < 41420 we find αn − 1.853 < r_{n} < αn + 0.780. The differences between successive terms were found to be 1, 2 or 3, with frequencies 0.317, 0.658, 0.024.)

It is unknown whether we have monotonicity here: Is it true that if f(q, r) = q and f(q′, r′) = q′ and r < r′, then q < q′?

8.7 Heuristics

If it is true that d_{n} and r_{n} behave like αn and q_{n} behaves like βn then one should expect the sequences d_{n} and q_{n} to be complementary: If a value x occurs on the diagonal, then approximately in row α^{−1}x = (2 − \sqrt{2})x, about 0.6x. If x is the start of a constant row, then this happens approximately in row αβ^{−1}x = x/\sqrt{2}, about 0.7x. Since 0.6x < 0.7x, the latter would have been excluded by the former, except possibly for very small x.

8.8 Estimates

It is possible to get a linear upper bound for q_{n}.

Claim: q_{n} ≤ 3n − 1.

We have to show that if q ≥ 3n − 1 then among the numbers f(q, r) there are at least n that are not larger than q. Let us call a number c a constant when it occurs as the value of a constant row, i.e., when f(c, r) = c for some r. The claim is that there are at least n constants c ≤ 3n − 1.

Suppose not. Pick m = 2n − 1. There are fewer than n constants c ≤ 3n − 1, so looking at the m + 1 values f(m, r) we see fewer than n values at most m, so more than n values larger than m, and hence f(m, m) ≥ 3n. At least n of the values 1, ..., 3n − 1 do not occur among f(0, 0), ..., f(m − 1, m − 1), but fewer than n are constants, so one of these values must occur on the diagonal later, say as f(u, u). We have m < u < 3n − 1 (the latter since f(u, u) ≥ u + 1) and fewer than n values f(u, r) are at most u, so more than u + 1 − n are larger than u, so that f(u, u) ≥ 2u + 2 − n ≥ 3n + 2. But f(u, u) ≤ 3n − 1 by definition, a contradiction.

8.9 Encyclopedia

Sloane’s encyclopedia of integer sequences [11] discusses these sequences and some related ones under numbers A029899-A029905.

Sequence A029899 is the number of P-positions [p, q, r] with 0 ≤ r ≤ q ≤ p ≤ n.

Sequence A029900 is the diagonal sequence (d_{n})_{n}.

Sequence A029901 is the sequence (q_{n})_{n}.

Sequence A029902 is the sequence (r_{n})_{n}.

Sequences A029903, A029904, A029905 are defined as p_{n}, q_{n}, r_{n} such that there exists a one-parameter family of P-positions [k +p_{n} +q_{n}, k +q_{n}, r_{n}] for k = 0, 1, 2, ... Sloane mentions the conjecture that Sequence A029905 is complementary to Sequence A029902, that is, that every row either becomes constant or becomes periodic with period 1. As we have seen, this is false, and 120 is the smallest number that is neither in A029902 nor in A029905.

8.10 Element frequencies

We find that if c = q_{n} and c < 100000, then there are precisely n pairs (q, r) with q < c and f(q, r) = c. These pairs have c − n ≤ q ≤ c − 1.

For the diagonal elements there is approximate linear behaviour: d_{n} occurs approximately n/2 times.

8.11 Row minima

Let m_{r} = min{f(q, r)|q > r}, and let k_{r} be the (smallest) q for which f(q, r) = m_{r}.

Claim: The sequence m_{r} is non-decreasing.

Consider the position (k, s) where s > r and k ≤ k_{s}. The value f(k, s) differs from the values earlier in column k and from the diagonal values f(m, m) with m < s. If f(k, s) < m_{r}, then the value f(k, s) was not excluded at the (k, r) position: it differs from earlier elements on diagonal and column, and also differs from the other row elements since it is smaller. This is a contradiction.

So, m := min(m_{s}, f(s, s)) ≥ m_{r}. Suppose we have equality, and pick k minimal so that m = f(k, s). Since m was not found at the (k, r) position, we must conclude that k > k_{r}. This shows that when row minima stay the same, the column in which they occur increases.

If a row minimum is the start of a constant row, that is, when m_{r} = f(k, r) with k = m_{r}, then m_{s} > m_{r} for s > r since the constant row blocks all further columns.

It is unknown whether the start of a constant row must be the off diagonal row minimum. This question is equivalent to that about monotonicity of the set of (q, r) forming the start of a constant row.

If it is true that the start p of a constant row must be the off diagonal row minimum, then it follows that it cannot occur on the diagonal (not earlier, because that would exclude p, and not later because the constant row is the last row in which p occurs). Thus, under this assumption f(p, r) = p and f(q, q) = p cannot both hold, and the winning move in [p, p, p] is unique.

8.12 Summary

We investigated the 3 × n Chomp by introducing a function of two variables which describes the P-positions. This function can be displayed in a two-dimensional chart, and the investigation of this chart is equivalent to the investigation of 3 × n Chomp. With the analysis of this chart we obtained several results for the game easily, e.g., there are infinitely many winning moves in the third row.

Several questions remain open for the 3 × n Chomp. The most interesting one is to prove that there is a unique winning move from the initial position. For this it is enough to prove that the series d_{n} and r_{n} are asymptotically αn and q_{n} is asymptotically βn for α = 1 + \frac{1}{\sqrt{2}} and β = 1 + \sqrt{2}. Another open problem is to prove the monotonicity of f(q, r), which is equivalent to the uniqueness of the winning move from the initial position, and also equivalent to the statement that every start of a constant row must be the off diagonal row minimum.

References

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

[2] Andries E. Brouwer, The game of Chomp.

   http://www.win.tue.nl/~aeb/games/chomp.html

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

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

   http://www.math.unibas.ch/~draisma/recreational/graphchomp.pdf

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

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

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

[8] Martin Gardner, Mathematical Games, Scientific American, Jan. 1973, pp. 110–111. (See also ibid. May 1973.)

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

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

[11] N.J.A. Sloane, Encyclopedia of Integer Sequences.

   http://www.research.att.com/~njas/sequences/index.html