David Gale's Subset Take-Away Game
J. Daniel Christensen, Mark Tilford · American Mathematical Monthly · 1997
Subset take-away is a two-player game involving a fixed finite set A. Players alternately choose proper, non-empty subsets of A, with the condition that one may not name a set containing a set that was named earlier.A player who is unable to move loses.For example, if A = {1}, then there are no legal moves and the second player wins.If A = {1, 2}, then the only legal moves are {1} and {2}.Each is a good reply to the other, and so once again the second player wins.The first interesting case is when A = {1, 2, 3}.In response to any first move, the second player may choose the complementary set.This produces a position equivalent to the starting position when A = {1, 2} and thus leads to a win for the second player.With increasing patience, the reader may enjoy verifying that when A has fewer than 6 elements, the game is a second player win.Indeed, David Gale, whom we understand deserves credit for this game, made the following conjecture [1].