Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]

POLYA020: Chomp  (proposed by Stephen C. Locke; 12/5/01).

Around 1950, Fred Shuh proposed a game he called the game of divisors. Two players, P_1, and P_2, agree on a positive integer N, and construct the list L_0 of all divisors of N. They alternate turns, with the person who makes the last move losing. At each turn, the player chooses a number x from the current list L_k, and deletes x and all of the divisors of x from the list. (For example, starting with N=24, the original list is L_0={1,2,3,4,6,8,12,24}. If P_1 takes x=4, then L_1={3,6,8,12,24}. A few minutes though might tell you this is a losing move, and that P_1 should really just have taken x=1). If N>1, it is fairly obvious that P_1 has a winning strategy, yet nobody knows the details of that strategy in general.

Problem A: What is a good strategy?
Problem B:  Suppose that we allow the player to delete either the divisors of x or the multiples of x. What can be said about a wining strategy? Can P_1 still force a win?

Discussion. [SCL, 12/6/01]:  Both Gale and Shuh give proofs (the same one of corse) that the first player has a win N=p^kq^j, for primes p,q, and integers non-negative i,j, not both zero. Also, both authors display the winning strategy when k=j, or when k=0 or k=1.
One of things that is interesting/curious about the case k=2 is that two (presumably) infinite sequences crop up. We can think of the case k=2 as consisting of a 3 by (j+1) chocolate bar, and a move being a breaking off of some piece of the chocolate bar, together with all cells to the righ and
above. The personn who takes the poisoned lower left piece loses.
In the study of the winning strategies, the chocolate bar at some stage will have top row with a cells, middle with b cells and bottom with c cells, a\le
b\le c. We call this position (a,b,c).
Now, for some a, there are an infinite number of choices for b, c; for some other a, there are only a finite number of choices.

Infinite a families:
 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

Finite a families:
 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

How can one generate these sequences without actually playing the game? If we could accurately predict the entries in the sequences, perhaps it would help in determining a solution to the game. As far as I know, nobody has completely solved the 3 by n game.
Then again, perhaps the sequences are really too sporadic to be predicted. Maybe the best one could hope for is to find the limit of R_m=F_m/I_m, where is the number of a\le m with the a family finite, and I_m is the number of a\le m with the a family infinite.
Here, R_80 = 47/33 =1.42424242....

[APH: 12/6/01]: This sequence is found in Sloane's _EIS_:

ID Number: A029905
Sequence:  0,2,5,7,9,11,14,17,19,22,24,26,28,31,34,36,38,40,42,45
Name:      r(n), where exists one-parameter family of strategic partitions
               (k+p(n)+q(n), k+q(n), r(n)) for k = 0,1,2,... in Chomp.
Conjectured to  be complementary to h(n), see A029902.
References: [3], [4] below.
See also:  See also A029899 - A029905.
Author(s): Fred Lunnon (fred@cs.may.ie)

Bibliography. [1] F. Shuh,  Spel van Delers (Game of Divisors),  Nieuw Tijdschrift voor Wiiskunde, 39 (1951-1952).??.
[2] D. Gale, A curious Nim-type game,  American Mathematical Monthly, 81 (1974)  876-879.
[3] E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways,  vol. 2, 598-600.
[4] M. Gardner, Mathematical Games, Sci. Amer. (Jan, May 1973).
Return to [Polya Home Page] [Members] [Problem Center] [Inventory] [Reserve Area]