Last weekend at the beach my nephew showed me an interesting situation he encountered while playing the card game SET. (Yes, this is the same nephew– who is brilliant, by the way– from last month’s puzzle.) The game is played with a deck of 81 cards, with each card showing 4 *features*, where each feature has 3 possible *values*:

- Shape (ovals, squiqqles, or diamonds)
- Number (1, 2, or 3)
- Color (red, purple, or green)
- Shading (solid, striped, or outlined)

The rules are simple. Deal 12 cards face-up on the table, and look for a *Set* of 3 cards that, for each feature, are either all the same or all different. The first player to identify a Set removes the 3 cards from the table, and 3 more are dealt. Once the entire deck is dealt, the player who collects the most Sets wins.

It is possible that 12 cards may not contain *any* Set, in which case 3 more cards are dealt… but those 15 cards may *still* not contain any Set, in which case 3 *more* cards are dealt, etc. The instructions included with the game suggest that “there are ~33:1 odds that a SET is present in 12 cards, and ~2500:1 odds when 15 cards are on the table.”

Despite these apparently long odds, my nephew’s family encountered such a collection of 15 cards that did not contain any Set:

15 cards that do not contain a Set… or do they?

(*Edit*: Thanks to reader Jafeth in the comments below, who pointed out that this collection of 15 cards actually *does* contain a Set!)

Are such Set-less collections really that rare? It turns out that they are not– not by a long shot– for several reasons. The least interesting reason is that the probabilities quoted in the instructions are simply not accurate. For example, the odds of a random collection of 12 cards not containing a Set are only about 30:1, not 33:1.

But the more interesting reasons are… well, as usual, I think this makes an excellent programming problem. Consider simulating this game, and estimating the probability that a collection of 15 cards does not contain a Set. (One of the many interesting challenges in this problem is concisely and efficiently implementing the condition of “being a Set” or not.) I think simulating the game like this exposes the “real” reasons that Set-less collections occur much more frequently than you might think.

### Like this:

Like Loading...

*Related*

I’m getting ~30:1 for 12, just like you had said. For 15 cards, I’m actually getting worse odds than what’s stated by the rules, at ~2,712:1. For 18 cards, I’m very consistently getting 59,999,999:1. I ran 60 million trials 8 times (totaling 480 million) and had 8 setless deals, occurring exactly once in each run of 60 million.

81 choose 12 is about 71 trillion, which I estimate I could exhaustively search in about a week with my available computing resources if I *really* wanted an exact answer for 12. But I bet you’ve figured out the smart solution already anyway! 81 choose 15 is out of the question for an exhaustive search.

Here’s my code: http://pastebin.com/uTEMC5TB

Nice. When I wrote, “concisely and efficiently,” I had you in mind, and you didn’t prove me wrong :).

There are a couple of interesting things happening here. First, estimating small probabilities is hard. (Remember that lightning talk about confidence intervals?) Even with nearly half a billion trials, with only 8 successes, we still have surprisingly little confidence in our point estimate of P(Set-less). At the 95% level, the odds of 18 cards not containing a set could be anywhere from 30 million to one to 140 million to one. (For example, imagine simulating another 480 million trials, but with hasSet(cards) simply returning (Math.random() < 8e-9), so that you *know* the small probability you are trying to estimate.)

Second, I over-simplified the rules somewhat for 15 cards. You're right that the stated probability (i.e., that 15 random cards do not contain a set) is ~1/2700 (although we should wrap a confidence interval around this estimate as well). But the two observations that I found interesting are (1) we only ever *see* 15 cards in the game when 12 of them already do not contain a Set, and (2) we continue to play the game dealing through the entire deck.

(1) implies that we are really interested in the *conditional* probability that 15 cards do not contain a Set, given that the original 12 *also* do not. This is the probability that I suggested is much higher than that quoted in the instructions.

(2) also affects the probabilities, not just for 15 cards but even for 12 cards, in an interesting and difficult-to-analyze-other-than-via-simulation way. That is, if we refine the simulation slightly to actually deal through the deck, and removing Sets as we "find" them, we find that the overall probabilities of encountering Set-less collections of cards increases quite a bit.

Ah, I understand the situation much better now. You’re talking about the chances of arriving at a 15-card setless deal

at some point during gameplay, not just in the initial deal. Here’s a new version that simulates an entire game.http://pastebin.com/DnqXzar0

Playing 1 million games (this is much slower), 16,195 times a 15-card setless deal was on the table. Of all the times three new cards were needed to be dealt, there was a ~1:1480 chance there were 15 cards on the table. It was ~15:1 for 12 cards. Here is the full histogram:

{ 0: 18574, 3: 1169002, 6: 10468884, 9: 10808463, 12: 1518882, 15: 16195 }

About 1.52% of games saw a 15-card setless deal. That’s ~65:1 — a fairly likely occurrence!

Set forms a 3^4 hypercube. You can show 2^4 cards without a set – one more than contemplated above. Just for each dimension, pick one value to omit entirely. That’s 3^4 possibilities out of 3^4! / (3^4 – 4)!, but that’s only one family of solutions.

You can get other families of solutions by “skewing” the indexing of the dimensions, eg instead of shape * number for two of them, use shape+number * shape-number.

I may be misunderstanding your comment, but you can realize quite a few more than 2^4=16 cards without a set– the maximum number of cards that might not contain a set is 20 (i.e., with at least 21 cards, there *must* be a set).

Hmm. I don’t see it. Do you have an example of 20 cards with no set?

There is a good paper by Davis and Maclagan (linked from the corresponding Wikipedia entry) that shows an example of 20 cards without a Set (page 3, Figure 3).

Thank you for that link. Very enlightening.

The example of 15 cards does contain a set: A3 B3 en B5

You’re right! Three and a half years later, you are the first to look closely enough to point this out. I have edited the post accordingly.

Pingback: The hardest 24 puzzles | Possibly Wrong