Triangulation Takeaway

MATHEMATICAL RECREATIONS by Ian Stewart

Scientific American, September 2000

The tradition of explaining mathematics through games and puzzles goes back at least to the ancient Babylonians, whose clay tablets include puzzles in arithmetic that would be entirely acceptable as 'word problems' today. The rapid growth of whole areas of new mathematics has given rise to entirely new games, whose rules cannot easily be stated without invoking concepts that would have been quite alien to the Babylonians, such as topology or set theory. In the 1996 book Games of No Chance (Cambridge University Press, editor R.J.Nowakowski) Richard K. Guy (Calgary) reported a game invented by David Gale (Berkeley), which starts out looking like a set-theoretic game and ends up as a topological one. The game holds plenty of interest for recreational mathematicians: for instance, it is still not known which player has a winning strategy, although Gale made a plausible conjecture. Moreover, it is easy to invent variations that are just as much fun to play.

Recall that the basic objects of set theory are sets, which are just collections of objects of some specified kind. The objects that belong to a set are its members, and are said to be contained in that set. If a set has finitely many members, then we can define it by listing the members inside curly brackets: for example \{ 2, 3, 5, 7 \} is the set of all prime numbers less than 10. A set X is a subset of a set Y if every member of X is a member of Y: for example, the set \{ 3, 5, 7 \} of all odd prime numbers less than 10 is a subset of \{ 2, 3, 5, 7 \}. Every set is considered to be a subset of itself; a subset of X is said to be proper if it is different from X. Sets can have one member, for example \{ 2 \}, the set of all even prime numbers. A set can even have no members, in which case it is said to be empty. An example is the set of all even prime numbers bigger than 3, which in curly bracket form would be \{ \; \}.

Gale's game is called Subset Takeaway. It starts with a finite set S, which we may as well take to be the set \{ 1, 2, \dots, n \} of whole numbers ranging from 1 up to n. Players alternately choose a proper, non-empty subset of S, subject to one restriction: no subset chosen earlier (by either player) can be a subset of the new subset. The first player unable to name such a subset loses.

One practical way to play the game is to draw up a set of columns on a sheet of paper, headed by the numbers 1, \dots, n, and mark a line of crosses in the columns that correspond to the selected subset. A new, legal move cannot include all of the crosses from some previous move. A more interesting way to represent the moves, which we'll come to shortly, is geometric — indeed, topological.

Following tradition, let the players be Alice and Bob, with Alice to move first. When n = 1 there are no legal moves. When n = 2 we have S = \{ 1, 2 \}. The only opening moves available to Alice are \{ 1 \} and \{ 2 \}, and whichever she chooses, Bob can choose the other. Then Alice is stuck, so Bob wins

When n = 3, we have S = \{ 1, 2, 3 \}. Suppose Alice chooses a subset with two members, say \{ 1, 2 \}. Then Bob can choose the complementary subset (everything not chosen by Alice) which here is \{ 3 \}. Now Alice can't choose anything that contains 3, so she has to select a subset of \{ 1, 2 \}, and from that point on the entire game is exactly the same as if the starting set had been \{ 1, 2 \}, since Bob can't choose any subset that contains 3 either. So again Bob wins. The same goes if Alice opens with any other two-member subset, for the same reason. However, Alice has another possible kind of opening: a one-member subset, say \{ 3 \}. Now Bob chooses the complementary subset \{ 1, 2 \}, and again the game must continue as if the starting set had been \{ 1, 2 \}, and Bob still wins. Since Alice's opening must be either a one-member subset or a two-member subset, Bob has a winning strategy: 'always play the complement of Alice's move'.

Before reading on, you may wish to consider whether the stame strategy gives Bob a win when n is larger than 3.

Enter the topology. Topology is usually described as 'rubber sheet geometry,' the study of properties of shapes that do not change when the shape is continuously deformed. Here, though, we don't need any elastic. Instead, we use one of the basic techniques in topology, which is — when possible — to triangulate the shape: that is, to split it up into triangles that join edge to edge. Strictly speaking, this description applies only to surfaces, but the same approach works for higher-dimensional shapes if we replace triangles by 'simplexes.' A three-dimensional simplex, or 3-simplex, for example, is a tetrahedron, with vertices 1, \, 2, \, 3, \, 4. It has four faces, six edges, and four vertices. The faces are triangles — 2-simplexes. The edges are line segments — 1-simplexes. And the vertices are points — 0-simplexes. Moreover, these bits of the 3-simplex correspond exactly to subsets of \{ 1, 2, 3, 4 \}. The tetrahedron itself corresponds to the whole set \{ 1, 2, 3, 4 \}. The faces correspond to the 3-element subsets \{ 1, 2, 3 \}, \{ 1, 2, 4 \}, \{ 1, 3, 4 \} and \{ 2, 3, 4 \}. The edges correspond to the 2-element subsets \{ 1, 2 \}, \{ 1, 3 \}, \{ 1, 4 \}, \{ 2, 3 \}, \{ 2, 4 \}, and \{ 3, 4 \}. And the vertices correspond to the 1-element subsets \{ 1 \}, \{ 2 \}, \{ 3 \}, \{ 4 \}.

In the same way, an (n-1)-simplex can be identified with the set \{ 1, 2, \dots, n \}, and its various lower-dimensional faces (from now on we use this term irrespective of their dimension) can be identified with subsets whose size exceeds the dimension by 1.

We can now reformulate Subset Takeaway as Simplex Erasure. Players start with a simplex. A move consists of choosing a proper sub-simplex of any dimension, and erasing its interior, as well as all higher-dimensional sub-simplexes that have it as a face. However, the boundary of the chosen sub-simplex — all of its faces — still remain.

We can use this topological representation to analyse Simplex Erasure for a 3-simplex, which corresponds to Subset Takeaway for n = 4. The starting position is a complete 3-simplex, that is, a tetrahedron. Because the complete set \{ 1, 2, 3, 4 \} is an illegal move, this tetrahedron is 'hollow' — its interior is not available as a move. Figure 1 shows a series of legal moves (diagrams of this type, built up from simplexes of various dimensions, are called simplicial complexes).

Figure 1: A typical game for a set with four members.

A systematic consderation of all such sequences shows that there is a winning strategy for Bob in the n = 4 game. The same goes for n = 5, \, 6, and Gale was led to conjecture that whatever the value of n, Bob has a winning strategy. To the best of my knowledge this is not yet proved or disproved. In 1997 J. Daniel Christiansen (MIT) and Mark Tilford (Caltech) applied more sophisticated ideas from topology to come up with a technique known as 'binary star reduction,' which can be used to simplify the game's analysis in certain circumstances ('David Gale's Subset Takeaway Game', American Mathematical Monthly 104 (October 1997) 762-766). Suppose that at some stage during the game we arrive at a position (represented by a simplicial complex) in which there are two vertices x and y that form a binary star — meaning that three conditions are valid:

• The edge \{ x, y \} is not present.
• If X is any subset of the game position that contains x, and if x is then replaced by y, the resulting subset is also a subset of the game position.
• If Y is any subset of the game position that contains y, and if y is then replaced by x, the resulting subset is also a subset of the game position.

Figure 2: What goes wrong with the complementary strategy.

So the 'complementary' strategy fails because it does not specify a legal move. However, with proper strategy, Bob still wins when n = 4. Christiansen and Tilford conjecture that for all n, Bob's correct response to any opening move by Alice is to choose the complementary subset for his first move. Thereafter, however, he may be forced to deviate from choosing the complement of Alice's move, as we've just seen. A similar game can be played on any simplicial complex. It might be hoped that whenever the game is played on some triangulation of a simplex (that is, a simplicial complex obtained by subdividing a simplex) then it is a win for Alice (not Bob). Indeed if this were true it would imply Gale's conjecture (I leave you to work out why, and why it is Alice who we might expect to win). However, Figure 3 shows such a triangulation in which Bob wins — again I leave it to you to work out why.

Figure 3: Bob wins on this simplicial complex, too.

Computer searches may well prove or disprove Gale's conjecture for n = 7, \, 8, or other small values. For larger n, what's required is a new idea.