Set (game)

Set is a game played with cards that each contain four attributes, where each attribute takes on one of three possible values. The goal of the game is to find sets (hence the game's name) of three cards, such that for each of the four attributes, either all three cards have different values or all three cards have the same value.

The cards have different numbers, colors, shapes, and textures, forming a set

Each card contains four attributes, each of which take on three values:

• Number: each card contains either 1, 2, or 3 shapes.
• Color: the shapes on each card are either red, green, or purple.
• Shape: the shapes on each card are either ovals, diamonds, or squiggles.
• Texture: each shape is either hollow, shaded, or filled.

Each combination of attributes corresponds to exactly one card, for a total of 81 cards in the deck. At any time, 12 cards are revealed, and the fastest player to find a set within these 12 cards wins the set (depending on the players, the penalty for a false set claim can range from being unable to claim a set again that round to losing an already won set). The three cards in the set are then removed, and another three cards are revealed, with the game continuing until the deck is completed.

Additionally, if no player is able to find a set within the group of 12 cards after some time, another three cards are revealed (with the agreement of all players). The next set claimed will not be replaced, since there will already be at least 12 cards showing. As shown below, it is indeed possible (though somewhat unlikely) that a group of 12 cards contains no set; in fact, it is possible for a group of up to 20 cards to contain no set.

Though the game of set is highly based on pattern recognition, there are a number of approaches used to speed up the searching process.

Analyzing a board:

Firstly, chances are very high that some attribute will be under-represented, in the sense that it is quite likely that (for example) there will be only one or two shaded cards in play. This means that sets involving those cards can be checked quite quickly, and if (as is most likely) they are not involved in any sets, any three cards that form a set necessarily have the same value for that attribute: in the previous example, any set would have three cards with filled shapes or three cards with hollow shapes.

Similarly, the chances are high that some attribute will be over-represented, in the sense that it is quite likely that (for example) there will be many cards with ovals with play. This means that it is often worth examining only possible sets containing these cards, as this guarantees one attribute will be satisfied (and there will be many more possibilities for the remaining three to be satisfied).

Transitioning between boards:

The most important part of the game is the period when the three new cards are revealed, as the players have already performed a significant amount of analysis on the 9 cards already showing.

Firstly, it is not unusual for the remaining 9 cards to themselves contain a set, so it is certainly worth analyzing the remaining cards for this reason alone. However, even more can be learned by anticipating possible useful cards: for instance, an over-represented attribute (e.g. a lot of ones) within the 9 cards means that an additional card with the same attribute is very likely to complete a set.

Finally, when the new cards are revealed, they are likely to be the ones involved in the set (should one exist), since the players will have already analyzed the 9 showing cards and discarded (or removed) sets from this pool of cards.

The mechanic of adding three additional cards when no set is possible leads to two natural questions:

• What is the probability that it will be necessarily to add three cards?
• What is the largest number of cards that can be revealed such that there is no set among them?

Both of these questions are answered by interpreting the game of set geometrically: each card can be viewed as an element of \(\mathbb{F}_3^4\), which basically means 4-D points of the form \((a_1, a_2, a_3, a_4)\) where \(a_i=1,2,\) or 3 for each \(i\). For instance, the point \(1, 2, 3, 1\) could correspond to "one green hollow squiggle".

The geometric interpretation of a set is then quite nice: three cards form a set if their associated points form a line.

Significant work is still necessary to solve the case of 4 attributes, but the situation is fairly easy to analyze when there are only 2 attributes (making the space \(\mathbb{F}_3^2\)). In such a situation, the question of the largest number of cards that contains no set is answered by the 2-dimensional geometric interpretation: what is the maximum number of integer points \(x,y\) with \(0 \leq x \leq 2, 0 \leq y \leq 2\) such that no three form a "line", where a line can "loop around"?

All three colors represent lines in \(\mathbb{F}^2\)

It is not too difficult to show that the maximal number of points (squares in the above picture) that do not form any line is 4:

Two examples of four points with no lines

Suppose it were possible to find 5 points, no three of which are collinear. Then each horizontal line contains at most 2 points, and so some horizontal line contains exactly one point (call it \(P\)).

There are four lines going through \(P\):

• \(H\), the horizontal line through the point
• \(V\), the vertical line through the point
• \(D_-\), the down-right diagonal line through the point
• \(D_+\), the up-right diagonal line through the point

Since \(H\) contains no points other than \(P\), and each point other than \(P\) is on exactly one of these lines, exactly one of \(V, D_+, D_-\) contains two points other than \(P\) (by the pigeonhole principle), and thus contains three collinear points -- a contradiction.

Hence there is no collection of 5 points in \(\mathbb{F}_3^2\) with no three collinear, making the maximum 4.

This type of reasoning gets more difficult to work with in higher dimensions, but the general strategy remains the same. In \(n\) dimensions, the maximum number of cards with no set is:

which, as applied to the traditional set game, means that it is possible to find 20 cards with no set^[1].

20 cards that contain no set

Even higher dimensions are more difficult to work with and require additional tools from the field of Ramsey theory. A recent (as of 2016) breakthrough shows that the maximal size of a cap set (a collection of cards with no set) in \(n\) dimensions has size at most \(\left(\frac{2.756}{3}\right)^n\), which has applications as far-reaching as quicker matrix multiplication algorithms.

The other question, regarding the probability of this occurring, is best answered by computer program. Knuth provides the following numbers^[2].:

which, in the typical 12-card case, gives the answer of slightly less than \(\frac{1}{30}\).

1. Davis, B., & Maclagan, D. THE CARD GAME SET. Retrieved April 2nd, 2016, from https://web.archive.org/web/20130605073741/http://www.math.rutgers.edu/~maclagan/papers/set.pdf
2. joriki, ?. In the card game Set, what's the probability of a Set existing in n cards?. Retrieved April 2nd, 2016, from http://math.stackexchange.com/q/203146