Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The card game Set has very simple rules (see here for rules), and it has prompted mathematicians to ask several questions. I will describe one of these questions. When the game ends, there are usually some left over cards, none of which form a Set; but occassionally it happens that the remaining cards all match up, and there are no left over cards. Call such a situation a "perfect" game. My question is:

What is the probability of having a perfect game? What are the best known upper and lower bounds for this probability?

Here we assume that if there are multiple sets available, then one is selected at random (with uniform probability among all distinct available sets). According to this handout the exact value for the probability of a perfect game is "very open". Anecdotally, I've probably played Set hundreds (maybe thousands?) of times, and only a handful have been perfect games (one of which was earlier today!).

A related question one could ask is whether or not the actual gameplay changes the probability. What I mean is:

Say all 81 cards are laid down face up, and Sets are removed randomly until no Sets remain. Is the probability of having no left over cards the same as it is when the game is played normally?

I could remark that the actual game of Set is a special case of a larger class of games, where the cards have n attributes each with r possible values; the usual game is the case n=4 and r=3. One could ask the same questions for this larger class of games. Also, these questions are more naturally viewed as questions about configurations of lines in affine space, but I've chosen to stick with the card game terminology.

share|improve this question
    
You have to make some choices about which nice properties to drop if you want to extend Set to a deck with more than $3$ possible values. –  Douglas Zare May 30 '11 at 0:06
    
As for the question, why not use a Monte Carlo test? –  Douglas Zare May 30 '11 at 0:10
    
Because I personally find provable bounds more interesting.. –  Anonymous May 30 '11 at 0:55
1  
Looking at $12$ cards, and then extending this to $15$ or $18$ or $21$ if there are no Sets, is quite messy. I would be surprised if you could not get much more accurate estimates from a simulation than you would from pure deduction. –  Douglas Zare May 30 '11 at 2:04
    
One way to get rigorous bounds for the main problem is to note that you have to go through some state with $18$ cards left (with some $12$, $15$, or all $18$ on the table). So, if you analyze all subsets with $18$ cards left which sum to $\vec{0}$ and choose a visible subset then you can get bounds on the probabilities. However, determining the probability of a perfect game for each one seems expensive, even $81 \choose 18$ is huge, and I think the bounds you get are weak. –  Douglas Zare May 30 '11 at 14:28
add comment

2 Answers 2

I have simulated playing 10 million games of Set, and for those simulations 1.2% of the games were perfect games (when selecting randomly among the available Sets the whole game). The full results from the simulations are here.

share|improve this answer
add comment

At the end of a game there will be 0,6,9,12,15 or 18 cards left. Here are the results of 10000 trials (assuming that Maple's random processes are random enough and I wrote it correctly)

  • $[[0, 88], [6, 4126], [9, 4732], [12, 1036], [15, 18]]$ with a full deck.

  • $[[0, 119], [6, 4454], [9, 4592], [12, 824], [15, 11]]$ with the standard rules.

I guess I would lean toward there not being a difference although it is not as convincing as it could be.

In a game with 9 cards (say red diamonds) there is no way to avoid taking all the sets. If you want to do an analysis then perhaps first try 27 cards (say the red cards). If you can't analyze that then there is little chance of handling 81 cards.

An analysis of the structure of the cards left behind might also be useful. For example if there are 6 cards left then there are 15 cards (counting multiplicity) not present which would create a set with two of the 6 cards. Is that usually 15 distinct cards or 5 cards three times each?

share|improve this answer
    
Thanks for the comments. Those numbers are certainly about what I would expect.. you'd probably have to run it quite a few more times to be confident in whether or not there's a difference. And precise statements about the bounds still seem out of reach.. –  Anonymous May 30 '11 at 16:09
add comment

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.