| DAVID GALE’S SUBSET TAKE-AWAY GAME (2002) | |||||||||||||||
Abstract | |||||||||||||||
| 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]. Conjecture 1. Subset take-away is always a second player win. It was pointed out to us by Richard Stanley that the collection of legal moves at any given time forms an abstract simplicial complex: if X is a subset of A that is legal, then every non-empty subset of X is also legal. To translate this into geometry, view a k-subset as a (k − 1)-simplex. If A = {1, 2, · · · , n}, then the starting position corresponds to the boundary of the (n − 1)-simplex. A move in this formulation of the game consists of choosing a simplex of any dimension, and erasing its interior as well as all higher-dimensional simplices having it as a face. For example, the starting position for the n = 4 game is a hollow tetrahedron, and after the move {1, 4} (which we write 14 for brevity) we have the position 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||