The transformer that provides electricity to the AMS building in Providence went down on Sunday, April 22. The restoration of our email, website, AMS Bookstore and other systems is almost complete. We are currently running on a generator but overnight a new transformer should be hooked up and (fingers crossed) we should be fine by 8:00 (EDT) Wednesday morning. This issue has affected selected phones, which should be repaired by the end of today. No email was lost, although the accumulated messages are only just now being delivered so you should expect some delay.
Thanks for your patience.
[Note: This is the first of two of David Austin's columns about SET. Also see "Game. SET. Polynomial."]
SET® is one of the rare card games simple enough for children to play and rich enough to keep adults engaged. After playing a few games, interesting combinatorial questions appear whose study reveals the game's elegant mathematical structure.
On each SET card is printed a number of symbols, as seen on these typical cards.
The game centers around four features of the symbols--their color, number, shape, and shading. There are three possibilities for each feature.
Color: | |||
Number: | |||
Shape: | |||
Shading: |
Since there are three possibilities for each of the four features and each card's combination of these four features is unique, there are $3^4 = 81$ cards in a deck.
Three cards are said to form a set if each of the four features, considered individually, is the same on each card or different on each card. For instance, these three cards form a set because each card has the same number (two) and the same shading (solid) but no two cards have the same color or shape.
After turning 12 random cards face up, players score points by identifying and removing sets. Here is a typical hand:
One set from the hand above is shown below. There are three more sets, and readers may benefit from spending some time looking for them. (You may play online as well.)
If we are given two cards, there is a unique third card that creates a set. For instance, if the first two cards share the same color, then so must the third. However, if the shapes on the two cards are different, then the third card must contain the remaining shape.
Using this observation, one may find all the sets in a hand by considering each pair of cards and checking whether the third card that forms a set with that pair is in the hand.
Sometimes, the twelve cards turned face up contain no set. In this case, the rules require that three more cards be turned face up giving a total of fifteen cards. If there is still no set, three more cards are turned face up and so forth.
After playing the game for a while, two natural questions appear, which we will explore: "How many cards need to be turned face up to guarantee the presence of a set?" and "What is the probability that the initial twelve cards do not contain a set?"
Shown here is a hand with 20 cards that contains no set.
As we'll see, it takes 21 cards turned face up to guarantee that there is a set. Curiously, this was discovered in 1971, a few years before SET was invented, by Pellegrino in a somewhat different context. We will explain this fact along the lines of Davis and Maclagan's elegant proof.
By the way, the probability of finding a hand of 20 cards with no set, like the one above, is just a little more than $10^{-13}$.
For the time being, let's focus only on the cards that are green and solid and arrange them so that two cards in the same row have the same shape and two cards in the same column have the same number. Notice that three cards lying on a line, whether horizontal, vertical, or diagonal, form a set.
Conversely, if we fill up the plane by placing copies of this $3\times3$ grid next to one another, we see that every set lies on a line as well.
This suggests that we may interpret sets as lines in an appropriate context. To make this precise, we use the field ${\Bbb F}_3=\{0,1,2\}$, in which the result of adding or multiplying two numbers is the remainder of the usual sum or product of integers after dividing by 3. For instance, 2 + 2 = 1 in ${\Bbb F}_3$ since the remainder of 2 + 2, when divided by 3, is 1. It is useful to note that $2 = -1$ in ${\Bbb F}_3$ since $1 + 2 = 0$.
For each feature of the SET cards, we associate the three possibilities with an element of ${\Bbb F}_3$. More specifically, the variable $x_1$ will take on values 0, 1, or 2 depending on the color of the card. There is no preferred way to set up this association so we choose that $x_1=0$ will denote a red card, $x_1=1$ a green card, and $x_1=2$ a purple card.
In the same way, we use a variable $x_2$ to record the shape choosing $x_2=0$ to denote an oval, $x_2=1$ a squiggle, and $x_2=2$ a diamond. Similarly, variables $x_3$ and $x_4$ record the number and shading.
Putting together these associations for each of the four features, we may represent a SET card by a 4-dimensional vector $(x_1,x_2,x_3,x_4)$ in the vector space ${\Bbb F}_3^4$.
A simple algebraic condition tells us when three cards form a set. Notice that adding an element in ${\Bbb F}_3$ to itself three times gives 0; that is, $x+x+x = 0$ in ${\Bbb F}_3$. In the same way, adding three elements, each of which is distinct from the others, gives 0 since $0+1+2 = 0$. In other words, three elements of ${\Bbb F}_3$ that are either all the same or all distinct sum to 0.
Conversely, suppose that $x$ and $y$ are distinct elements of ${\Bbb F}_3$. Then, $x + y + y = x + 2y = x - y \neq 0$.
Putting these two observations together, we obtain an algebraic description of a set:
Cards $c_1$, $c_2$, and $c_3$ in ${\Bbb F}_3^4$ represent a set precisely when $c_1+c_2+c_3 = 0$.
Notice that this condition tells us explicitly how a pair of cards determines the third member of the set; given a pair of cards $c_1$ and $c_2$, then $c_3 = -c_1-c_2$ completes the set.
This condition may also be understood geometrically.
Three points $c_1$, $c_2$, and $c_3$ lie on a line precisely when there is a scalar $\lambda$ such that $$ c_3 - c_1 = \lambda(c_2-c_1). $$ Since there are three scalars $\lambda$ in ${\Bbb F}_3$, each line in ${\Bbb F}_3^4$ has three points.
If $c_1$, $c_2$, and $c_3$ are distinct points in ${\Bbb F}_3^4$, they lie on a line precisely when $$ c_2-c_1 = 2(c_3-c_1) = 2c_3 - 2c_1 = -c_3-2c_1. $$ which is the same as our algebraic condition: $$ c_1+c_2+c_3 = 0. $$
This leaves us with the pleasing fact that
Sets correspond to lines in ${\Bbb F}_3^4$.
Using this correspondence, we may rephrase the question "How many cards need to be turned face up to guarantee a set?" as "How many points in a subset of ${\Bbb F}_3^4$ guarantee a line in that subset?"
Before digging into this question, let's spend a little more time thinking about geometry in ${\Bbb F}_3^d$ as some combinatorial ideas that will soon be helpful arise naturally.
In the more familiar Euclidean geometry, we know that two points determine a unique line. We have seen that this is also true in ${\Bbb F}_3^d$: two points $p$ and $q$ in ${\Bbb F}_3^d$ determine a unique line by adding the third point $r = -p-q$.
Let's look more closely in two dimensions, $d=2$, at ${\Bbb F}_3^2$, which contains nine points.
If $p$ is a point in ${\Bbb F}_3^2$, there are eight other points, each of which determines a line through $p$. However, each of these lines contains two points besides $p$ so we have $8/2 = 4$ lines through $p$.
Now suppose that $L$ is a line and $p$ is a point not on $L$. Since there are three points on $L$, each of these points determines a line through $p$ intersecting $L$. Therefore, the fourth line through $p$ does not intersect $L$. As before, this means that the Euclidean parallel postulate holds for this geometry: If $L$ is a line and $p$ a point not on $L$, there is a unique line through $p$ parallel to $L$.
In three dimensions, ${\Bbb F}_3^3$, there are 27 points, which means there are $(27-1)/2 = 13$ lines passing through a given point $p$.
We may also consider planes in ${\Bbb F}_3^3$, each of which contains nine points.
As usual, two planes are either parallel or intersect in a line. Given a line $L$ in a plane $P$, there are six points in $P$ that are not on $L$. Therefore, if we are given a line $L$, there are 24 points in ${\Bbb F}_3^3$ not on $L$, which implies that there are $24/6 = 4$ planes in ${\Bbb F}_3^3$ containing the line $L$.
We would also like to count the number of planes containing a given point $p$. We have seen that there are 13 lines through $p$ and each line is contained in four planes. Counting naively, this would lead us to believe there are $13\cdot 4$ planes containing $p$. However, if $P$ is such a plane, we have seen that there are four lines containing the point $p$, which means we have counted each plane containing $p$ four times. Consequently, there are $13\cdot 4/4 = 13$ planes containing $p$.
Let's now return to our original question about the game SET: "How many cards turned face up guarantee a set?" This is equivalent to asking "What is the largest set of cards in which there is no set?" or "What is the largest subset of ${\Bbb F}_3^4$ that contains no line?"
We will build up to this question by first answering the same question in lower dimensions ${\Bbb F}_3^d$. By a $d$-cap, we mean a subset of ${\Bbb F}_3^d$ containing no lines. We call a $d$-cap of the largest possible size maximal and denote its size by $m_d$.
${\mathbf d=1}$: This case is simple. Since ${\Bbb F}_3^1$ consists of a single line,
a maximal 1-cap contains two points, meaning $m_1 = 2$.
${\mathbf d=2}$: We no longer have a cap if we add any point to the 2-cap shown below.
We makes us think that $m_2 = 4$ so let's suppose we have a cap $C$ of ${\Bbb F}_3^2$ with five points.
Considering the "horizontal" lines $H_1$, $H_2$, and $H_3$, it must be the case that $C$ intersects two of the lines, say $H_1$ and $H_2$, in two points and the third line $H_3$ in a single point $p$.
We have seen that there are four lines containing $p$. One of these four lines, $H_3$, contains no other points of $C$. Therefore, the other four points of $C$ must lie on the three remaining lines through $p$. The Pigeonhole Principle implies that one line, say $L$, must contain two other points of $C$ in addition to $p$. Therefore, the line $L$ must be in $C$, which means that $C$ cannot be a cap.
In this way, we have shown that $m_2=4$.
If we try to add points to the following 3-cap, which contains nine points, we begin to suspect that $m_3 = 9$.
To see that this is true, Davis and Maclagan are guided by the ideas we saw when $d=2$; in that case, we divided ${\Bbb F}_3^2$ into three parallel lines and counted the points in the intersections of these lines with the cap $C$.
Davis and Maclagan consider families $P_1$, $P_2$, and $P_3$ of parallel planes in ${\Bbb F}_3^3$, of which the family of three horizontal planes is an example. Since each family of parallel planes has a plane containing the origin, the number of such families equals the number of planes containing the origin. We saw that there are 13 planes containing a given point so there must be 13 families of three parallel planes in ${\Bbb F}_3^3$.
Now suppose that $C$ is a 3-cap with ten points. Notice that any plane $P$ in ${\Bbb F}_3^3$ intersects $C$ in a 2-cap. Therefore $P\cap C$ has four or fewer points.
If we have a family of three parallel planes $P_1$, $P_2$, and $P_3$, consider the cardinalities $|P_1\cap C|$, $|P_2\cap C|$, and $|P_3\cap C|$, each is which is no more than four. Since $C$ has ten points, there are two possibilities:
Two planes in the family intersect $C$ in four points and one plane in two points. We call this a $(4,4,2)$-family.
Otherwise, two planes intersect $C$ in three points and one plane in four points, giving a $(4,3,3)$-family.
The number of $(4,4,2)$-families is denoted $x_{442}$, and the number of $(4,3,3)$-families $x_{433}$. Since there are a total of 13 families, we have $$ x_{442} + x_{433} = 13. $$
Davis and Maclagan show how to obtain a second equation involving $x_{442}$ and $x_{433}$ by introducing a 2-marked plane, a pair $(P, \{p,q\})$ consisting of a plane $P$ and two points $p$ and $q$ in $P\cap C$.
We first count the number of 2-marked planes, beginning with a pair of points $p$ and $q$ in the cap $C$. Since $p$ and $q$ determine a unique line $L$ and there are four planes containing $L$, we know there are four 2-marked planes containing $p$ and $q$. Since the number of pairs of points in $C$ is $_{10}C_2 = 45$, there are $45\cdot 4 = 180$ 2-marked planes.
Now suppose we have a $(4,4,2)$-family of parallel planes $P_1$, $P_2$ and $P_3$, labeled so that $|P_1\cap C| = |P_2\cap C| = 4$ and $|P_3\cap C| = 2$. Since $_4C_2 = 6$, there are six 2-marked planes containing $P_1$ and six 2-marked planes containing $P_2$. Since $_2C_2=1$, there is one 2-marked plane containing $P_3$.
In this way, a $(4,4,2)$-family contains $6+6+1 = 13$ 2-marked planes. Similarly, a $(4,3,3)$-family contains $6+3+3=12$ 2-marked planes. This means that $$13 x_{442} + 12x_{433} = 180.$$
We therefore have the pair of equations \[ \begin{align*} x_{442} + x_{433} & = 13 \\ 13x_{442} +12x_{433} & = 180 \end{align*} \]
whose solution is $x_{442} = 24$ and $x_{443} = -11$. Since $x_{442}$ and $x_{433}$ must be nonnegative integers, we have encountered a contradiction to our assumption that the 3-cap $C$ has 10 points. Therefore, $m_3 = 9$.
Earlier, we saw a hand of 20 SET cards without a set, which means that $m_4 \geq 20$. After taking care of a few more details, the same ideas we used to argue that $m_3 = 9$ allow us to conclude that $m_4 = 20$.
Assuming that we have a cap $C$ with 21 points, we consider families of three parallel hyperplanes $H_1$, $H_2$, and $H_3$. Counting these as before shows that there are 40 such families.
The intersection of a hyperplane $H$ with $C$ is a 3-cap so this intersection must contain nine or fewer points. Therefore, we characterize a family of three parallel hyperplanes by the numbers of points in the intersections of the hyperplanes with $C$. This separates the families into $\{i,j,k\}$-families where \[ \{i,j,k\} = \{9,9,3\}, \{9,8,4\}, \{9,7,5\}, \{9,6,6\}, \{8,8,5\}, \{8,7,6\}, \{7,7,7\}. \]
If $x_{ijk}$ is the number of $\{i,j,k\}$-families, then the fact that there are 40 families of hyperplanes says that \[ x_{993} + x_{984} + x_{975} + x_{966} + x_{885} + x_{876} + x_{777} = 40. \]
Counting both 2-marked hyperplanes and 3-marked hyperplanes leads to the equations: \[ \begin{align*} x_{993} + x_{984} + x_{975} + x_{966} + x_{885} + x_{876} + x_{777} &= 40 \\ 75x_{993} + 70x_{984} + 67x_{975} + 66x_{966} + 66x_{885} + 64x_{876} + 63x_{777} &= 2730 \\ 169x_{993} + 144x_{984} + 129x_{975} + 124x_{966} + 122x_{885} + 111x_{876} + 105x_{777} &= 5320. \end{align*} \]
With a little work, it can be shown that there are no nonnegative integer solutions of these equations, which means there cannot be a 4-cap with 21 points. This shows that $m_4 = 20$.
As mentioned earlier, the fact that a hand having 21 cards must contain a set follows from an earlier result of Pellegrino. This fact could also be seen by checking each hand with 21 cards; of course, the problem is that there are $_{81}C_{21} = 13,636,219,405,675,528,192$ such hands. Regardless, Van Brink claims to have used a computer program, running on a 90MHz Pentium machine for about a week in 1997, to check that every hand of 21 cards contains a set.
To do this, we could use the natural symmetries of the SET deck to reduce the possible hands that need to be checked. If we permute the colors of the cards in a hand, for instance, we would not change whether a given hand contains a set. Since we can permute each feature and we can permute the features, there are a total of $3!^4 \cdot 4! =$ 31,104 symmetries that can be used to simplify the problem.
In fact, there is a larger group of symmetries that helps reduce the problem even further. Since an affine transformation of ${\Bbb F}_3^4$ carries lines into lines, such a transformation will not affect whether a subset contains a line. An affine transformation of ${\Bbb F}_3^4$ has the form $x\mapsto Ax + b$ where $A$ is an invertible $4\times4$ matrix in ${\Bbb F}_3$ and $b$ is a vector in ${\Bbb F}_3$.
To form $A$, we need a basis $\{v_1,v_2,v_3,v_4\}$ for ${\Bbb F}_3^4$. There are 81-1 choices for $v_1$, which must be nonzero; 81-3 choices for $v_2$, since it must not lie on the line defined by $v_1$; 81-9 choices for $v_3$, since it must not lie on the plane defined by $v_1$ and $v_2$; and 81-27 choices for $v_4$. Similarly, there are 81 choices for $b$. This gives a symmetry group with $ (81-1)\cdot(81-3)\cdot(81-9)\cdot(81-27)\cdot81 = $ 1,965,150,720 elements.
In his program setset
, which ran on my 2.70GHz laptop in three minutes, Knuth uses this symmetry group to check that every set of 21 cards must contain a set and to enumerate all the hands of 20 or fewer cards that do not contain a set. He finds, for instance, that there are 2,284,535,476,080 hands of 12 cards without a set. Since there are $_{81}C_{12} = $ 70,724,320,184,700 hands having 12 cards, approximately 3% of the hands initially dealt in the game of SET do not contain a set.
Moreover, Knuth's program counts the number of setless hands that are not equivalent to one another under the action of the affine transformation group. For instance, there is essentially only one hand of 20 cards that does not contain a set; that is, given any two setless hands of 20 cards, there is an affine transformation that carries one hand into the other.
Here is a tabulation of Knuth's results. For each $n$, we state the number of setless hands $S_n$ with $n$ cards, the number of hands $D_n$ that are distinct under the group of affine transformations, and the fraction of hands $F_n$ that are setless.
$n$ | $S_n$ | $D_n$ | $F_n$ |
1 | 81 | 1 | 1.0 |
2 | 3240 | 1 | 1.0 |
3 | 84240 | 1 | 0.987 |
4 | 1579500 | 2 | 0.949 |
5 | 22441536 | 3 | 0.876 |
6 | 247615056 | 7 | 0.763 |
7 | 2144076480 | 11 | 0.617 |
8 | 14587567020 | 33 | 0.454 |
9 | 77541824880 | 91 | 0.297 |
10 | 318294370368 | 267 | 0.169 |
11 | 991227481920 | 670 | 0.082 |
12 | 2284535476080 | 1437 | 0.032 |
13 | 3764369026080 | 2225 | 0.010 |
14 | 4217827554720 | 2489 | 0.002 |
15 | 2970003246912 | 1756 | 3.64e-04 |
16 | 1141342138404 | 748 | 3.40e-05 |
17 | 176310866160 | 143 | 1.37e-06 |
18 | 6482268000 | 20 | 1.42e-08 |
19 | 13646880 | 1 | 9.01e-12 |
20 | 682344 | 1 | 1.45e-13 |
21 | 0 | 0 | 0.0 |
As we followed Davis and Maclagan's argument, we found the size of a maximal cap $m_d$ as $d$ increased from 1 to 4. There is no reason to stop there; we could imagine that the SET cards have a fifth feature, such as texture, and play the game with a deck of $3^5 = 243$ cards.
While Davis and Maclagan's methods do not allow us to determine the size of a maximal 5-cap, a result of Edel, Ferret, Landjev, and Storme shows that $m_5 = 45$. Once again, they look at families of hyperplanes and count the number of points in the intersections of these hyperplanes with a subset of ${\Bbb F}_3^d$. Interestingly, they use the Fourier transform to study these counts and relate them to the number of lines contained in that subset.
The SET website says this about the inventor of SET, Marsha Jean Falco, and the origins of the game.
Marsha was a Population Geneticist who was trying to understand whether epilepsy in German Shepherds is inherited. To study the genes and chromosomes in the dogs? cells, Marsha created file cards with blocks of information for each dog. Because certain blocks of information were the same on each file card, she drew symbols to represent blocks of data, rather than writing out the data. She used symbols with different properties to represent different gene combinations. While explaining the combinations to the veterinarians she was working with, Marsha decided there could be some fun in the combinations of symbols and SET was born. Over the years, Marsha refined the game by playing with her family and friends and it was finally released in 1990.
It is remarkable how such a simple game leads to interconnected ideas in linear algebra, finite geometry, combinatorics, and analysis.
Benjamin Davis, Diane Maclagan. The card game SET. The Mathematical Intelligencer. Volume 25, Number 3, pages 33-40. 2003.
Giuseppe Pellegrino. Sul massimo ordine delle calotte in $S_{4,3}$. Matematiche. Volume 25, pages 149-157. 1970.
Donald Knuth. The programs setset
, setset-all
, and setset-random
.
Jürgen Bierbraur and Yves Edel. Bounds on affine caps. Journal of Combinatorial Designs. Volume 10, Issue 2, pages 111?115. 2002.
Y. Edel, S. Ferret, L. Landjev, L. Storme. The classification of the largest caps in $AG(5,3)$. Journal of Combinatorial Theory, Series A. Volume 99, Issue 1, pages 95?110. 2002
The AMS encourages your comments, and hopes you will join the discussions. We review comments before they're posted, and those that are offensive, abusive, off-topic or promoting a commercial product, person or website will not be posted. Expressing disagreement is fine, but mutual respect is required.
Welcome to the Feature Column!
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .