Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given $n$ randomly drawn Set cards on a table from a standard 81-card deck, how can I determine the probability of one or more Sets existing on the table?

First, for those who may not be familiar with the game, here's a simple introduction to Set (see setgame.com), which lends itself to some straightforward mathematics: there are four properties of the symbols on each card. Each property has three states, resulting in $3^4$ or 81 possible symbols. Each of the 81 cards is unique.

The properties are as follows: Number, Shading, Color, and Shape.

  • The three states of Number: One, Two, Three.

  • The three states of Shading: Open, Lined, Solid.

  • The three states of Color: Red, Green, Purple.

  • The three states of Shape: Diamond, Oval, Squiggle.

A Set is defined by three cards in which each property is either all the same across the three cards (e.g. Two, Two, Two), or all different across the three cards (e.g. Red, Green, Purple). You must consider all four properties when determining the validity of a Set.

Hence the following are Sets:

  • One Lined Red Diamond, Two Lined Green Diamonds, and Three Lined Purple Diamonds
  • One Solid Green Oval, One Solid Green Diamond, One Solid Green Squiggle
  • One Lined Purple Squiggle, Two Solid Red Diamonds, Three Open Green Ovals.

And, just for kicks, the following is not a Set:

  • One Open Green Diamond, Two Lined Green Diamonds, and Two Solid Green Diamonds; the number property does not pass the test (1, 2, 2)

The game is played by one or more players placing twelve cards (random, from a shuffled deck) face up on a flat area. When a player sees a Set, s/he calls "Set" and indicates the three cards, collects them from the table, and the dealer replaces them. When the deck runs out, and no more Sets are possible, whoever has the most Sets wins.

Hopefully you have the gist of it now. Here's the question again, in light of the rules: given a shuffled 81-card deck, when you lay out $n$ cards face up on a table, what is the probability of a Set existing on the table?

I have been able to figure it out to five cards, but past that, I get lost. I'll post what I have in an answer, because it's part of the answer, but what I really want to know is whether there's an easier way to do it. Otherwise it could take me a long time, no kidding.

share|improve this question
    
One note that may be useful: given three items $A$, $B$, $C$ with properties $A=\left\langle A_N, A_F, A_C, A_S\right\rangle$, etc. (I'm using **F**ill instead of Shading for obvious reasons) where each property is taken from some arbitrary assignment of values to $(0\ldots 2)$ (e.g., 'Open=0, Lined=1, Solid=2', then $A$, $B$ and $C$ form a set if and only if $A_i+B_i+C_i\equiv 0\pmod 3$ for $i\in\left\{N,F,C,S\right\}$. This doesn't change the number of tests you have to do, but it may make testing faster. –  Steven Stadnicki Sep 26 '12 at 20:56
    
Also, note that you can speed up your tallies by using a variant of branch-and-bound techniques: while building all six-card possibilities, for instance, if you hit a set on the first three cards then you know that all six-card possibilities with those three cards are legal, and you can simply add the appropriate number of combinations to your total rather than iterating over them all individually. This should let you push your counts up a few more $n$. –  Steven Stadnicki Sep 26 '12 at 20:59
    
@Steven: I thought of using this optimization, but as long as roughly half of all combinations don't contain a set, I don't think this would change the run time by more than a small factor, since we still have to visit each combination without a set. –  joriki Sep 26 '12 at 21:01
    
Is there any insight gained from lowering the problem to be about some smaller $\mathbb{F}_3^n$ (rather than $\mathbb{F}_3^4$)? –  alex.jordan Sep 26 '12 at 22:05

3 Answers 3

up vote 3 down vote accepted

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} $$

share|improve this answer
    
I wonder if there is a closed function to describe these values given n=number of cards. Also, can the program output fractions? (I accepted this answer since it gives the values I was after.) –  Daniel Sep 28 '12 at 18:06
1  
@Daniel: I suspect that Knuth put some thought into finding a closed form before he went to all that trouble to write and debug those programs, so if there is a closed form it's probably hard to find. I don't quite understand your question about fractions -- I quoted the output of the program verbatim; the results are counts of combinations and hence integers, so I don't see how fractions enter into it. In case you meant the numbers in the table; those are not output by the program; I generated them by dividing by $\binom{81}n$, and you can express that division in fractions if you prefer. –  joriki Sep 30 '12 at 13:30
    
Of course - sorry for not noticing the integers ;). So now I'm completely answered except for the closed form, which appears to be next to impossible to find. Also, what does the list of "cases" e.g. (2489 cases) etc. mean? –  Daniel Nov 7 '12 at 15:30
    
@Daniel: I think it means the number of equivalence classes under symmetry operations. I think it's all explained in the WEB program. –  joriki Nov 7 '12 at 16:06

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:

  1. With three cards, $\frac{1}{79}$ of the time, there will be a Set.
  2. 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.
  3. 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%.

share|improve this answer

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$.

share|improve this answer
    
My suggestion for summing in large sets of combinations rather than iterating over them should work here, too, and let you push these figures a fair bit higher; I can't write up the app right now, unfortunately, but may try when I get home if I have time. –  Steven Stadnicki Sep 26 '12 at 21:01
    
@Steven: Our comments crossed; see my comment under your comment under the question :-) –  joriki Sep 26 '12 at 21:02
    
@joriki under what?)))))))))) –  Seyhmus Güngören Sep 27 '12 at 0:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.