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