My
Set obsession is still going strong. Set (in case you haven’t already seen it) is a simple
pattern-matching game in which players try to identify sets (or “SETs”) of three cards that are either all the same or all different in each of four attributes: color (red, green, purple), shape (diamonds, pills, tildes), shading (open, hatched or solid) and number (one, two or three). I’ve been practicing on a Web site
on which you can play Set for free (with registration). It’s amazing how steep the learning curve gets after an initial burst of improvement in speed that comes with learning to identify SETs. Set seems to fit the “easy to learn, difficult to master” mold. Playing it with other people, however, I quickly realized that Set, like tennis, is most fun by far when people of similar skill are competing.
I’m still trying to figure out a mathematical solution to the question, “What is the probability that twelve Set cards drawn at random don’t have a SET?” That will take more thinking yet, but in the meantime I’ve considered some easier problems. In so doing I discovered how much one can learn playing tic-tac-toe.
Having a visually/spatially-oriented brain, I like to think of the 81 cards in the Set deck as a
four-dimensional space that can be expressed as nine 3×3 tic-tac-toe squares. By assigning an attribute to each dimension and always keeping the three values (colors, shapes, etc.) in the same order, one can arrange the Set cards to form a 3×3×3×3 “magic square” (a 4-dimensional hypercube, actually), as shown in Plate 1. Other arrangements are possible, but most are
not nearly as intuitive.
To save space, not to mention bundles of time making pictures, I’ll also use a text shorthand for the 3×3 matrices, using Xs or other letters for specific cards and periods as placeholders. For instance, the SET
may be expressed as
X . .
. X .
. . X,or
A . .
. B .
. . Cto refer to specific cards within the SET.
Another way to envision the deck, as I
described previously, is to assign each attribute to one digit in a four-digit number, and to replace the values with the numerals 1 to 3, yielding numbers from 1111 to 3333.
With the preliminaries out of the way, I’ll prove the Fundamental Theorem of Set. I purloined the Theorem (but not its name) from the
official Web site.
Theorem. Given any two cards in the Set deck, there is exactly one card that can be added to complete a SET.
Proof: Choose two cards at random-say, these:
Because the symbols on these cards have different colors, any card that completes a SET with them must have a different color yet; so it must be red. Similarly, we have two different shapes, so the third card must have the remaining shape-diamonds. The shadings are different, too, leaving the one remaining shading, solid, for the third card. Finally, both cards have one symbol, so the last card must have the same. We’re left with only one choice-a single, red, solid diamond:
In the general case, using the numerical notation, if we have cards a1a2a3a4 and b1b2b3b4 (where all as and bs are 1, 2 or 3), then the third card is c1c2c3c4 such that, for i = 1, 2, 3, 4,
ci = ai = bi if ai = bi, and
ci ≠ ai and ci ≠ bi if ai ≠ bi.
Either way, there exists precisely one choice for ci, i = 1, 2, 3, 4, and hence, precisely one card that will complement the first two.
The Fundamental Theorem leads to a number of useful facts. Two of them are simple corollaries:
Corollary 1. The Set deck contains exactly 1,080 different SETs.
Proof: If we choose two cards from the deck, there are 81 possibilities for the first card (the total number of cards) and 80 possibilities for the second; and by the Fundamental Theorem, each of these pairs determines one SET. There are, then, 81 × 80 = 6,480 different ordered SETs. Note, however, that because we chose the cards in a specific sequence, and because order doesn’t matter in differentiating SETs, we’ve counted each SET more than once. If A, B, and C form a SET, we’ve tallied {A, B, C}, but also {A, C, B}, which is the same SET-not to mention {B, A, C}, {B, C, A}, {C, A, B} and {C, B, A}. What works for this SET works for any: hence, each unique SET is represented in our grand collection in six different permutations. The number of unique SETs, therefore, is (81 × 80)/6 = 1,080.
Essentially the same proof is presented in “
Developing Mathematical Reasoning Using Attribute Games” by A. L. Quinn et al., Mathematics Teacher 92 (1999), 68-75.
Corollary 2. If three cards are drawn at random from the complete deck, the probability that they form a SET is exactly 1 in 79.
Proof: How many ways can we choose three cards from the deck, whether or not they constitute a SET? Again, we have 81 choices for the first card, and 80 for the second; but now we don’t care what the third card is, so any of the 79 remaining will do. Again, order doesn’t matter, so we need to divide the total by 6 to find the unique combinations: (81 × 80 × 79)/6 = 85,320. Of these 85,320 possibilities, 1,080 are SETs; so the probability of choosing a SET is 1,080/85,320 = 1/79. (We could have taken a shortcut with the math, and have noted that the number of SETs and total combinations differ by a factor of 79. Edit: Or we could have taken an even shorter cut, and noticed that of the 79 possibilities for the third card, exactly one completes a SET, as per the Fundamental Theorem.)
I did think of this myself, but as it happens I got scooped by the same Quinn et al. article (embedded in the answer to Question #5).
Thanks to the magic of combinatorics we know how many SETs we can find in the full deck. But can we count all the possible SETs? Are all the SETs contained in the magic hypercube of Plate 1?
Referring back to the magic hypercube, playing Set is analogous to playing four-dimensional tic-tac-toe-sort of. In Plate 1, you can convince yourself any winning tic-tac-toe combination, in any direction in any or all of the four dimensions, is a SET. It is only sort of like four-D tic-tac-toe because “wraparound” diagonal tic-tac-toes are also legal SETs. Two such examples (using only the first two dimensions) are
X . .
. . X
. X .and
. X .
. . X
X . .corresponding to the SETs
Finding wraparound SETs is equivalent to finding SETs by the regular rules of tic-tac-toe and then exchanging particular rows and columns (including the third- and fourth-dimensional analogues to “rows” and “columns”).
Some theories of the cosmos posit that three-dimensional space is curved in higher dimensions in such a way that it is infinite but bounded: if you travel far enough in one direction, you’ll “wrap around” and wind up back where you started. The Set space is infinite but very strictly bounded: every SET spans the known universe!
For clarity, let’s number the dimensions: the first two dimensions will be defined by rows (1) and columns (2) within the nine 3 × 3 matrices: a row contains three cards of the same color, symbol and shading but different in number, and a column, three cards of the same color, symbol and number but different shading. So, if you like, dimensions 1 and 2 index number and shading, respectively. Suppose that dimensions 3 and 4 index shape and color, respectively. Here,
A . . B . . C . .
. . . . . . . . .
. . . . . . . . .
D . . . . . . . .
. . . . . . . . .
. . . . . . . . .
E . . . . . . . .
. . . . . . . . .
. . . . . . . . .cards A, B, C form a row in the third dimension, and cards A, D, and E a row in the fourth.
To begin enumerating the SETs in Plate 1, consider all the simple rows in all four dimensions. We have 27 rows in each dimension, and naturally, each is a valid SET; 108 in all. All SETs in this class contain three cards with one attribute different and all three others the same.
Now, consider diagonals within the first two dimensions. Each of the nine matrices contains three “slash” diagonal SETs with slope 1, shown below marked X, Y and Z. X is the usual tic-tac-toe diagonal and Y and Z represent the “wraparound” diagonals.
Y Z X
Z X Y
X Y ZIt also has three “backslash” diagonal SETs with slope -1. Again, X is the traditional diagonal, Y and Z are wraparound:
X Y Z
Z X Y
Y Z XWe have, then, six SETs of this type in each matrix, or 54 across all nine. The cards in all these SETs share two attributes-shape and color-and differ in the other two.
Now things get fun. We can do the same for diagonals in the other pairs of dimensions. Take dimensions 1 and 3. Here are three diagonals that share the attributes shape and number:
X Y Z Z X Y Y Z X
. . . . . . . . .
. . . . . . . . .and here are three more:
X Y Z Y Z X Z X Y
. . . . . . . . .
. . . . . . . . .These correspond to the “slash” and “backslash” diagonals within one 3 × 3 matrix. As for dimensions 1 + 2, we tally 54 SETs for dimensions 1 + 3 (six SETs per extended row of nine cards having the same color and shading, and nine extended rows of cards).
We have four more pairs of dimensions in which to count diagonals-1 + 4, 2 + 3, 2 + 4 and 3 + 4-and 54 SETs in each. Totaling up over all the SETs with two attributes the same, we get 54 × 6 = 324. Along with the 108 sets with three attributes in common, so far we’ve accounted for forty percent of the total 1,080 sets.
The next type of SET we can look at has one attribute the same and three different. Things start to get pretty loopy here. Begin with one SET in dimensions 1 + 2 + 3:
X . . . . . . . .
. . . . X . . . .
. . . . . . . . XAdd two more:
X . . Z . . Y . .
. Y . . X . . Z .
. . Z . . Y . . XThese sets have the same color but different everything else. The weirdness sets in when we see that now there are two ways to vary the direction of the diagonals. Here’s one way:
X . . Y . . Z . .
. Y . . Z . . X .
. . Z . . X . . Yand here’s the other:
. . Z . . Y . . X
. Y . . X . . Z .
X . . Z . . Y . .The final configuration, combining both differences, looks like this:
. . Z . . X . . Y
. Y . . Z . . X .
X . . Y . . Z . .Okay-how many SETs? If we populate the rest of the first case for the top row of matrices, we get nine SETs:
A D G C F I B E H
H B E G A D I C F
F I C E H B D G AYe gads! At this point it might help to look back at Plate 1 and convince yourself that these really are all SETs that share a common color but nothing else. Over all four different kinds of diagonals, we have 36 SETs in the top row of matrices (correspondingly, the color red). Similarly, we can add 36 SETs for the middle (green) and bottom (purple) rows; and thus the grand total for all SETs that share a common color is 108.
That’s for color; we must also consider number, shape and shading, each of which piles another 108 sets to our total, or 432 in all. Overall we now have 864-80% done!
You guessed it-we need now consider only the SETs that have no attributes in common. Now everything is diagonal, and we must attack all four dimensions simultaneously. Here, for the sake of space and sanity, I have to abandon the graphical approach and fall back on the numerical notation. These SETs may be counted exhaustively (NB: just thinking about them was pretty exhausting in itself) by counting the ways we can change the values of each attribute. I’ll define “incrementing” as adding 1 to the value of a given attribute, rolling 3 back around to 1: 1 → 2 → 3 → 1. Similarly, “decrementing” is subtracting 1, rolling 1 back to 3: 3 → 2 → 1 → 3. As shorthand, I’ll use “+” for “increment” and “-” for “decrement.”
Examine first the case of incrementing all four attributes (+ + + +). The sets {1111, 2222, 3333} and {1321, 2132, 3213} are examples. How many SETs do we generate by incrementing all the attributes? There are 81 choices for the first member of the set, but if we list all 81 we’ll count each SET three times, e.g.: {1111, 2222, 3333}, {2222, 1111, 3333}, {3333, 1111, 2222}. (Not six times! We’ll get to that in a sec.) So, we have 27 sets in this subclass (where by subclass, I mean the set of SETs defined by incrementing upward for all attributes).
We have another 27 in the subclass (+ + + -), e.g., {1111, 2223, 3332}, and in fact, 27 for each of the 16 combinations of increments and decrements: (+ + + +), (+ + + -), (+ + - +), and so on, up to (- - - -). But not all of them generate different SETs! Beginning with 1111 and applying (+ + + +) we get the SET {1111, 2222, 3333}; but applying (- - - -) we get the same SET: {1111, 3333, 2222}. Applying the precise opposite incrementing rule-(+ + + +) vs. (- - - -), or (- + + -) vs. (+ - - +)-has the effect of creating the same SETs in different orderings. We must, therefore discard half of the 16 incrementing rules. That leaves us with 27 (in each subclass defined by an incrementing rule) times 8 (incrementing rules) SETs, for a total of 216.
We’re done!
To recap: We’ve enumerated
108 SETs with three attributes in common
324 with two attributes in common
432 with one attribute in common, and
216 with none in common
for a total of 1,080, and all are found in the magic hypercube (we didn't look for the last category there, but if you can soldier through the wrapping around and dimension-changing, you'll see them). These numbers match the ones found in the Quinn et al. (1999) article using combinatorics.
To sum up, we’ve comprehensively described the game of Set using nothing but tic-tac-toe and counting-an example of “proof by naughts and crosses.”
I won’t try to prove that 20 cards is the largest number that can contain no SETs, (shown
here with real pictures), but I did want to compare my attempt at finding the maximum no-SET collection with the actual solution. Here is an example of a 20-card no-SET group on the hypercube:
X . X . X . . . .
. . . X . X . X .
X . X . X . . . .
. X . X . X . . .
X . X . . . . X .
. X . X . X . . .
. . . . . . . . .
. X . . X . . . .
. . . . . . . . .My collection of 16 cards is equivalent to this configuration:
X . X X . X . . .
. . . . . . . . .
X . X X . X . . .
X . X X . X . . .
. . . . . . . . .
X . X X . X . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .I was on the right track, but didn’t see the crucial step of twisting the squares into diamonds in the second level of the third and fourth dimensions. Close but no “see-gar,” as Albert the Alligator in the old Pogo comic strip would say.
Part III of Set™ Theory may be found
here. Thanks for reading!