In the card game Set, what's the probability of a Set existing in n cards?
It turns out that Don Knuth wrote programs to compute these values in 2001. The WEB programs are available here, and a WEB-to-C compiler is available here (it worked out of the box on my Mac). I ran the faster of the two programs, setset-all, in which Knuth used a much larger isomorphism group to make use of the symmetries. It only took a couple of minutes to complete on my Mac. Here's the output:
81 SETless 1-sets (1 cases)
3240 SETless 2-sets (1 cases)
84240 SETless 3-sets (1 cases)
1579500 SETless 4-sets (2 cases)
22441536 SETless 5-sets (3 cases)
247615056 SETless 6-sets (7 cases)
2144076480 SETless 7-sets (11 cases)
14587567020 SETless 8-sets (33 cases)
77541824880 SETless 9-sets (91 cases)
318294370368 SETless 10-sets (267 cases)
991227481920 SETless 11-sets (670 cases)
2284535476080 SETless 12-sets (1437 cases)
3764369026080 SETless 13-sets (2225 cases)
4217827554720 SETless 14-sets (2489 cases)
2970003246912 SETless 15-sets (1756 cases)
1141342138404 SETless 16-sets (748 cases)
176310866160 SETless 17-sets (143 cases)
6482268000 SETless 18-sets (20 cases)
13646880 SETless 19-sets (1 cases)
682344 SETless 20-sets (1 cases)
0 SETless 21-sets (0 cases)
Dividing by $\binom{81}n$ and subtracting from $1$ yields the following proportions of sets with Sets:
$$ \begin{array}{rc} 1&0.00000000000000\\ 2&0.00000000000000\\ 3&0.01265822784810\\ 4&0.05063291139241\\ 5&0.12411638993917\\ 6&0.23702812843386\\ 7&0.38339288958876\\ 8&0.54646648344183\\ 9&0.70277715297383\\ 10&0.83054958637630\\ 11&0.91824367776036\\ 12&0.96769802141450\\ 13&0.98997192274043\\ 14&0.99768669219781\\ 15&0.99963531493045\\ 16&0.99996602550906\\ 17&0.99999862737549\\ 18&0.99999998580641\\ 19&0.99999999999099\\ 20&0.99999999999985\\ 21&1.00000000000000\end{array} $$
This is not the full answer; I'm only posting it to show what I've tried to do so far. I'd like to know whether there's a pattern I can follow or whether there's at least an easier way to do it.
Here's what I have so far:
I realize that when you take two Set cards, they inexorably point to one and only one other card in the deck to complete the Set. For instance, if you have Two Lined Purple Diamonds and Three Solid Purple Squiggles, the third card must be One Open Purple Oval. So when I take two cards from the deck and lay them on the table, only one out of the remaining 79 cards will create a Set. This must be true with any selection of three cards. So the probability of a Set existing in 3 randomly selected cards is $\frac{1}{79}$ or ~$1.266$%.
Now for the fourth. Assuming that the previous three cards do not make a Set (which is true $\frac{78}{79}$ of the time, remember), then it must be true that each unique combination of two cards points to a third card which is still in the deck. I will refer to the cards as (1), (2), (3), etc, for brevity. So what I am saying is this: If (1) (2) (3) is not a Set, then the combination of (1) (2) points to one and only one third card which is still in the deck (we'll call it (a)). Likewise the combination of (2) (3) (we'll call the third card (b)) and of (1) (3) (the third can be (c)). Therefore, there are three cards (a), (b), and (c) still in the deck (which now has 78 cards), any of which if placed as the fourth card on the table will create a Set. However, the remaining 75 cards will not create a Set. So, for four cards: $\frac{1}{79}$ of the time, the first three will have been a Set; and $\frac{78}{79}$ of the time, there is a $\frac{3}{78}$ chance of the fourth card completing a Set. So the total probability is: $\frac{1}{79}+\frac{78}{79}\cdotp\frac{3}{78}$, which is $\frac{4}{79}$ or ~$5.063$%.
For the fifth, assuming that the previous four did not contain the Set (which is true $\frac{75}{79}$ of the time) I was tempted to simply look at the remaining 77 cards, imagine that 6 of them will fit with the four on the table (since there are 6 possible combinations of two cards in a group of four), and spout the number $\frac{6}{77}$. So it would be $\frac{1}{79}+\frac{78}{79}\cdotp\frac{3}{78}+\frac{78}{79}\cdotp\frac{75}{78}\cdotp\frac{6}{77}$. But that's not the case. I thought about it, then realized that sometimes, four cards can consist of two groups of two cards, each group of which points to the same third card to complete the Set. I had stumbled on the possibility of intersecting Sets. There is a name for four cards which would be intersecting Sets given the correct fifth card: it's called a MetaSet. It's handy that it's been christened, since the concept appears to be a prominent one in my subsequent calculations.
Here's an example of a MetaSet just in case I wasn't clear: One Solid Purple Squiggle, One Lined Green Squiggle, Two Open Red Diamonds, Three Open Red Ovals. The first pair of cards point to One Open Red Squiggle, and the second pair points to One Open Red Squiggle. So for some combinations of four cards which do not contain a Set (namely, MetaSets), only five of the remaining 77 cards will create a Set when placed on the table with them.
Using our card terminology established above, when the four cards (1) (2) (3) (4) are not a MetaSet and do not include a Set, there are 6 cards (a) (b) (c) (d) (e) (f) each of which when placed next to the four will create a Set:
- (1) (2) -> (a)
- (1) (3) -> (b)
- (1) (4) -> (c)
- (2) (3) -> (d)
- (2) (4) -> (e)
- (3) (4) -> (f)
But when there is a MetaSet:
- (1) (2) -> (a)
- (1) (3) -> (b)
- (1) (4) -> (c)
- (2) (3) -> (d)
- (2) (4) -> (e)
- (3) (4) -> (a)
Since (a) takes the place of two cards, there are only 5 cards in the remaining 77 which will create a Set when one is placed with the four on the table.
Now to figure out the probability of four cards being a MetaSet. Let's take three cards. $\frac{1}{79}$ of the time, they will be a Set. We're not interested in that right now, so we'll turn to the other $\frac{78}{79}$ of the time. Now we're working with three cards which do not form a Set. We'll start with (1) (2), which points to (a), still in the deck. Then we take (a) (3), which points to (A), in the deck. So now, if (A) was placed on the table, we'd have a MetaSet, since (1) (2) points to (a), and (3) (A) points to (a). There are two other ways to rearrange the cards to produce MetaSets:
- (1) (3) -> (b); (b) (2) -> (B)
- (2) (3) -> (c); (c) (1) -> (C)
So we have established that there are three cards (a) (b) (c) in the reminaing 78 which will create a Set with the three on the table, and three other cards (A) (B) (C) which create a MetaSet. So the chance of four cards containing a MetaSet at this point is $\frac{3}{78}$.
To try to wrap this monster up:
- With three cards, $\frac{1}{79}$ of the time, there will be a Set.
- Adding a card to the other $\frac{78}{79}$ of the possibilities will create a Set $\frac{3}{78}$ of the time, and a MetaSet $\frac{3}{78}$ of the time, with the other $\frac{72}{78}$ of the possibilities containing neither Sets nor MetaSets.
- Adding a fifth card to a non-MetaSet ($\frac{78}{79}\cdotp\frac{72}{78}$ of the time) will create a Set $\frac{6}{77}$ of the time, while adding a fifth card to a MetaSet ($\frac{78}{79}\cdotp\frac{3}{78}$ of the time) will create a Set only $\frac{5}{77}$ of the time.
Taking all this into consideration, the final number is: $\frac{1}{79}+\frac{78}{79}\cdotp\frac{3}{78}+\frac{78}{79}\cdotp(\frac{72}{78}\cdotp\frac{6}{77}+\frac{3}{78}\cdotp\frac{5}{77})$
$\frac{1}{79}+\frac{3}{79}+\frac{78\cdotp72\cdotp6+78\cdotp3\cdotp5}{79\cdotp78\cdotp77}$
$\frac{4}{79}+\frac{72\cdotp6+3\cdotp5}{79\cdotp77}$
$\frac{755}{6083}$
~$12.412$%
A computer program, brute-forcing the 25621596 unique combinations of 5 Set cards, came up with the same answer, and was able to give the fractions for 6 and 7 cards as well: $\frac{27395}{115577}$ (~$23.703$%) and $\frac{31651}{82555}$ (~$38.339$%), but brute-forcing takes too long beyond that. I know that by 20 cards, there's still a possibility of having no Set (see this paper for an example), but by 21, there's a 100% chance of having a Set.
My eventual goal is to list all the fractions and percentages of the chances of having a Set in 3 cards, 4 cards, 5 cards, all the way up to 20, past which I know it's 100%.
The brute-force approach can be carried a bit further by noting that we can fix two of the cards without loss of generality. Here's a program based on that approach. It reproduces your numbers and further yields $\frac{1669201}{3054535}\approx54.647\%$ for $n=8$ and $\frac{156705991}{222981055}\approx70.278\%$ for $n=9$.