Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I learned of this problem through Su Gao, who heard of it years ago while a post-doc at Caltech. David Gale introduced this game in the 70s, I believe. I am only aware of two references in print:

  • Richard K. Guy. Unsolved problems in combinatorial games. In Games of No Chance, (R. J. Nowakowski ed.) MSRI Publications 29, Cambridge University Press, 1996, pp. 475-491.
  • J. Daniel Christensen and Mark Tilford. David Gale's Subset Take-Away Game. The American Mathematical Monthly, Vol. 104, No. 8 (Oct., 1997), pp. 762-766.

The game depends on a finite set $A$, and is played by two players I and II that alternate, with I playing first. Each move is a subset of $A$. We are given a pool of available subsets, and each move should be a set in the pool. At the beginning, the pool consists of all subsets of $A$ except for $A$ and the empty set. Whenever a set is used in a move, it and all its supersets are removed from the pool. The game ends when the pool is empty, and the player that was to move and cannot (because there are no moves left) loses.

For example, if $|A|\le 2$, then II always wins. If $|A|\le 3$, there is an easy winning strategy for II. To see this, list the elements of $A$ as $a,b,c$ in such a way that the first move of I is either $\{a\}$ or $\{b,c\}$, and have II respond the other one. This means that when I comes to move again, only $\{b\}$ and $\{c\}$ remain, and II wins.

One can also check by hand that II has a winning strategy if $|A|\le 5$, and Christensen-Tilford showed the same when $|A|=6$, although they did not include the code used for their computer verification.

The conjecture is that II always has a winning strategy.

My question is whether there have been any further developments towards establishing this, or any additional references. Suggestions or related ideas are also welcome.

share|improve this question
add comment

3 Answers

up vote 18 down vote accepted

Hello! As Dr. Stanley said, I worked on this topic last summer, in large part expanding on the work of Draisma and Van Rijnswou at http://www.math.unibas.ch/~draisma/recreational/graphchomp.pdf. Draisma and Van Rijnswou addressed the special case of subset take-away where none of the given subsets have more than two elements (i.e. where you’re playing on a graph with individual elements as vertices and 2-element subsets as edges); they found nim-values for trees and complete graphs, and gave a method of simplification by involution which is similar to one of the lemmas I recall Christensen and Tilford demonstrating.

To be a bit more specific than the abstract Dr. Stanley linked to, my paper gives the following additional information about the case of playing on a graph: 1) nim-values for all bipartite graphs, dependent only on the parity of the number of vertices and the number of edges; 2) nim-values for all complete n-partite graphs, dependent on the residue mod 3 of the number of parts containing an odd number of vertices; and 3) (really nasty) nim-values for some odd-cycle pseudotrees (i.e. connected graphs with exactly one cycle, that cycle being odd).

Also, my paper generalizes Draisma and Van Rijnswou’s method of simplification by involution to all subset take-away games (so also generalizing Christensen and Tilford’s lemma).

None of this comes all that close to establishing who wins when all or almost all subsets are included, rather than just some 1- and 2- element ones. This is due to the game being insanely complicated—even some very simple-looking graphs follow very strange rules. Dealing with bigger subsets will probably require an entirely different approach from what has been done with graphs.

I never got around to putting the paper in a publicly available location, but it will happen at some point…


[Edit, March 8, 2013: The paper has been posted, "Chomp on Graphs and Subsets', by Tirasan Khandhawit, and Lynnelle Ye. arXiv:1101.2718.]

share|improve this answer
    
@Lynelle-Ye, thanks for answering on here. Please do make the paper available if at all possible. –  sleepless in beantown Oct 13 '10 at 1:02
    
Hi Lynnelle. Many thanks! –  Andres Caicedo Mar 8 '13 at 16:22
    
(Sorry for the delay in posting the link, I only found it recently.) –  Andres Caicedo Mar 8 '13 at 21:32
add comment

A high school student named Lynelle Lin Ye looked at this game as a summer research project. See page 12 of http://www-math.mit.edu/news/summer/2009RSIAbstracts.pdf. She also won a prize for this work from the Intel Science Talent Search. I don't know if this work is obtainable from the internet, but you could try to contact her or her adviser Tirasan Khandhawit.

share|improve this answer
4  
I've sent a link to this question to Lynnelle. –  Qiaochu Yuan Oct 12 '10 at 16:36
    
Many thanks! It would be nice to see the paper. I'll post an update if I find it. –  Andres Caicedo Oct 12 '10 at 21:21
    
I feel like an idiot knowing there are high school students doing this kind of research. Maybe MY kids will be raised right and have that kind of opportunity. –  Andrew L Oct 13 '10 at 16:54
2  
@Andrew: Lynnelle's research was done through the Research Science Institute (cee.org/programs/rsi), a competitive six-week summer program. The program really has done a lot to provide students with these kinds of opportunities; alumni on MO include myself, Harrison, Akhil, and Terence Tao (!). –  Qiaochu Yuan Oct 13 '10 at 17:57
    
@Qiaochu Gee,thanks,now I REALLY feel like an idiot. Sorry,a lot of late-starter regret and jealousy here,Pay me no mind. –  Andrew L Oct 14 '10 at 10:21
add comment

The game you describe is a sibling close relative of Schuh's Divisor Game, which is played on the set of all divisors of a positive integer $N$. For a description of the game, see Problem 12 of

http://math.uga.edu/~pete/NT2009HW1.pdf

This is the first problem set in an advanced undergrad number theory course I taught twice at UGA in recent years. If memory serves, I got the problem from Aaron Abrams, who used it when he taught the same course at UGA a few years before. It is absolutely one of my favorite problems in the whole course: I don't want to say that if you don't like this problem you're not going to like number theory or mathematics (but part of me feels this way!). Note that a paraphrase of part d) is that the unjustly more famous combinatorial game Chomp can be simulated by the divisor game. Since Chomp is already unsolved, so is the divisor game. Let me also remark that I actually had a student who wrote a computer program implementing and playing the divisor game for a final project in the course. She did a very nice job!

Schuh's divisor game can also simulate the subset take away game: let $N$ be a product of $n$ distinct primes.

[Added: I just looked more carefully at the rules of your game. I formulate these games in the misère version, meaning the person to make the last move loses. However it is equivalent to disallow the ability to take away everything at once, i.e., in this case to take the divisor $N$ of $N$ and all of its divisors. In the coming generalization, this means removing the maximal element from the poset. If the poset also has a minimal element, as it does for me, then a classic strategy stealing argument shows that the first player must have a winning strategy: he could just become the second player by taking the minimal element. However, in your version the minimal element is removed from the start, so it is equivalent to the first player having already played and taken the least element. It is easy to see that for general $N$ this need not be a winning strategy, e.g. consider the case of $N$ a prime power. For the case of squarefree $N$, as you say, it looks more likely that this is the beginning of a winning strategy.]

Still, it is interesting and useful to think about a yet more general game, the poset game which is described as problem (G2) in this set. (Note that one could get away with weaker finiteness conditions than just the finiteness of the entire poset, but I didn't want to push that point in a first number theory problem set.) The game that you describe is more visibly equivalent to the poset game played on the power set of a finite set, partially ordered by inclusion (or, indeed, by reverse inclusion).

You will see there that there has been another interesting science project math paper written about this subject, namely the following one by Steven Byrnes:

http://www.emis.ams.org/journals/INTEGERS/papers/dg3/dg3.Abstract.html

There is a nice theorem here, the poset game periodicity theorem!

In general, I find this to be an attractive corner of mathematics. It certainly seems like there is plenty of further work to be done.

share|improve this answer
    
This is very nice, thanks for the references! –  Andres Caicedo Oct 12 '10 at 21:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.