The Odds of Finding a Set in The Card Game SET

SET is a card game using a special deck of cards. Initially, 12 cards are dealt face-up into a shared 4×3 layout, like this:




Players simultaneously try to find a set of three cards. A set is defined as three cards in which each of the four features of the card (color, shape of symbols, number of symbols, and shading) have either all the same value or all different values.

For example, this is a set:


All three cards have different colors; all have different symbols; all have different numbers of symbols; and all have the same shading.

This is not a set:


All three cards have different colors; all are diamonds; all have one symbol; however, two have open shading and one is filled.

Set is a fun game, whether or not you have kids in middle school math class. (You can buy it here if you want; note it gets 85% 5-star reviews and 96% 4 or 5 stars.)

The rules say that when a set of three cards is found, the three cards are removed and replaced by three more from the deck. If at any point there is no set of three cards in the array, then 3 more cards are added. The instruction booklet says that the odds against there being no set in 12 cards is 33:1, and the odds against no set in 15 cards is a whopping 2500:1. However, in playing the game, we were stymied more often than that with 12 cards, and even once with 15 cards (as shown in this crappy cell-phone-photo):

So one of the following must be happening:

  1. We were unlucky to get a one-in-2500 array of 15 cards in our first day of playing.
  2. We didn't recognize a set that is actually there.
  3. The instruction book is completely wrong.
  4. The instruction book correctly gives the odds for an initial deal of 12 (or 15) cards, but in the course of playing the game, removing sets and adding more cards. the odds change.

I hoped that the answer was 4, and I built a simulation to check. Here are the results—First, when dealing 12 (or 15) cards into a fresh layout and checking whether there is a set, I get:

Size |  Sets  | NoSets | Set:NoSet ratio for initial layout
-----+--------+--------+----------------
  12 | 96,701 |  3,299 |   29:1
  15 | 99,962 |     38 | 2631:1
This agrees reasonably well with the ratios stated in the instructions (33:1 and 2500:1). But now if we simulate playing a game, removing sets and replacing them with new cards, and tallying how often there is or is not a set with an array of different sizes, we get:
Size |  Sets  | NoSets | Set:NoSet ratio for game play
-----+--------+--------+----------------
  12 | 86,260 |  5,692 |   15:1
  15 |  5,433 |     48 |  113:1
  18 |     47 |      0 | inft:1
These ratios are quite different. The chances for finding no set among 12 cards has doubled. And the odds of finding no set with 15 cards has jumped by 20-fold. Thus, it seems the answer is my choice 4—the odds change over th course of a game.

Two problems remain. The first is to update the odds in the instruction booklet. I've let the good folks at setgame.com know, and hope they can fix it in the next printing. But more interesting is the problem of why the odds change so dramatically. At first I thought it was because players were picking up the "good" cards to make sets, leaving the "poor" cards, which are less likely to make a set. But what makes a card good or poor? As Gregory Quenell points out in this presentation, each of the 81 cards participates in the same number of sets, 40, and each pair of cards participates in exactly one set. (That means there is a total of 1080 distinct sets: 81 × 80 × 1 / 3! = 1080.) So now I believe there is no such thing as a "good" card, or a "good" pair of cards. Instead, I think what is happening is that when he initial 12 cards are dealt, there might be 0, 1, 2, or more sets in the array. If there was 1, then when you pick up that set, you only get three chances to form a set with one of the new cards. So I did an experiment where I tallied the results only for layouts where there are no sets in the initial *n*-3 cards; I then add 3 cards and see if there is a set. Here's what I found:

Size |  Sets  | NoSets | Set:NoSet ratio for initial layout, but no sets before dealing last 3 cards
-----+--------+--------+----------------
  12 | 26,415 |  3,330 |    8:1
  15 |  3,294 |     36 |   92:1
The results for an array of size 15 is roughly the same as when we play the game normally, which it should be, because in playing the game normally we only go to 15 cards when there is no set in 12 cards. But the ratio for an array of size 12 shows half as many sets as in playing the game normally, and a quarter as many as the initial deal. I take this as evidence that supports my theory that the ratio of no-sets goes up as sets are removed from the array.
Peter Norvig