# Math question/the game Set **URL:** \ **Category:** Factual Questions\ **Created:** [July 3, 2003, 11:38pm UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147 "2003-07-03T23:38:53Z")\ **Posts on this page:** 14\ **Page:** 1
**Author:** ![Hubajube](https://avatars.discourse-cdn.com/v4/letter/h/c37758/32.png) [@Hubajube](https://boards.straightdope.com/u/Hubajube)\ **Post date:** [July 3, 2003, 11:38pm UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/1 "2003-07-03T23:38:53Z")
Any combinatorics people out there? There’s a popular card game named Set that won Mensa’s game of the year in 91. (There are rules and sample layouts [here](http://www.liveandlearn.com/educational/set.html).) We’ve been playing it lately, and I was wondering what the fewest number of cards would be that you could guarantee has a set. I can prove that a certain set of 16 cards contains no set, and I think the correct answer is 17, but I can’t necessarily prove it. Anyone want to take a shot? ---
**Author:** ![ElJeffe](https://avatars.discourse-cdn.com/v4/letter/e/958977/32.png) [@ElJeffe](https://boards.straightdope.com/u/ElJeffe)\ **Post date:** [July 3, 2003, 11:58pm UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/2 "2003-07-03T23:58:37Z")
Given the three different shapes, the three different numbers of objects per card, the three different colors, and the three different fill styles, is there exactly one card of each type possible? Jeff ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 4, 2003, 12:07am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/3 "2003-07-04T00:07:14Z")
I really have no idea even how to start, but maybe you could tell us the certain hand of 16 cards with no set in it? ---
**Author:** ![Hubajube](https://avatars.discourse-cdn.com/v4/letter/h/c37758/32.png) [@Hubajube](https://boards.straightdope.com/u/Hubajube)\ **Post date:** [July 4, 2003, 12:23am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/4 "2003-07-04T00:23:50Z")
> [@](#): > > \*Originally posted by ElJeffe \* > \*\*Given the three different shapes, the three different numbers of objects per card, the three different colors, and the three different fill styles, is there exactly one card of each type possible? > > Jeff \*\* Yes. The deck is 3x3x3x3=81 cards. ---
**Author:** ![Hubajube](https://avatars.discourse-cdn.com/v4/letter/h/c37758/32.png) [@Hubajube](https://boards.straightdope.com/u/Hubajube)\ **Post date:** [July 4, 2003, 12:27am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/5 "2003-07-04T00:27:07Z")
> [@](#): > > \*Originally posted by Achernar \* > \*\*I really have no idea even how to start, but maybe you could tell us the certain hand of 16 cards with no set in it? \*\* OK. Pick one type of each category. Let’s choose shape=diamond, count=3, color=red, and pattern=stripes. Now take the 81 card deck and discard all cards that have any of these, and you’ll have 16 cards left. Now any set must have at least one category that’s all-different. This is because if shape, count, color and pattern were all all-the-same, then you’d have 3 of the exact same card, and there’s only 1 of each card. Since we’ve discarded all of one of each category, we know that there are no all-differents in the 16 left over, so there’s no set. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 4, 2003, 12:49am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/6 "2003-07-04T00:49:48Z")
Well, the easy way to verify that 17 is the smallest is to take those 16 cards, add in each single card from the remainder, and find a set. We like to call this method perfect induction, as it sounds so much fancier than brute force. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 4, 2003, 1:02am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/7 "2003-07-04T01:02:45Z")
I think that would be pretty easy to do, **ultrafilter**. However, unless we know that every “valid” 16-card hand is of the form given by **Hubajube** , it’s not QED. ---
**Author:** ![biqu](https://avatars.discourse-cdn.com/v4/letter/b/7feea3/32.png) [@biqu](https://boards.straightdope.com/u/biqu)\ **Post date:** [July 4, 2003, 1:05am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/8 "2003-07-04T01:05:23Z")
The math department at my college interviewed several candidates last semester. One of the candidates presented a lecture on this very topic. The answer is 20, from what I remember. Let’s see if I can dig up a cite. > [@](#): > > **What is the maximum number of cards in a Set-less pile? Can you establish upper or lower bounds for this maximum?** > For approaches to this problem, see Question 7 in Developing mathematical reasoning using attribute games at [http://www.setgame.com/set/article\_nctm.htm](http://www.setgame.com/set/article_nctm.htm) . The answer to this question is 20. Examples of 20-card, Set-less piles are shown in the links at [http://setgame.com/set/mathtricks.htm](http://setgame.com/set/mathtricks.htm) . That 20 is also the upper limit was proven by A. Calderbank and P. Fishburn in Maximal three-independent subsets of {0, 1, 2}n, Designs, Codes, and Cryptography 4(3), 203-211, 1994. from [this page](http://www2.edc.org/makingmath/mathprojects/gameOfSet/set_results.asp) ---
**Author:** ![Hubajube](https://avatars.discourse-cdn.com/v4/letter/h/c37758/32.png) [@Hubajube](https://boards.straightdope.com/u/Hubajube)\ **Post date:** [July 4, 2003, 1:08am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/9 "2003-07-04T01:08:27Z")
> [@](#): > > \*Originally posted by Achernar \* > \*\*I think that would be pretty easy to do, **ultrafilter**. However, unless we know that every “valid” 16-card hand is of the form given by **Hubajube** , it’s not QED. \*\* Exactly. ---
**Author:** ![Hubajube](https://avatars.discourse-cdn.com/v4/letter/h/c37758/32.png) [@Hubajube](https://boards.straightdope.com/u/Hubajube)\ **Post date:** [July 4, 2003, 1:11am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/10 "2003-07-04T01:11:15Z")
> [@](#): > > \*Originally posted by amore ac studio \* > \*\*The math department at my college interviewed several candidates last semester. One of the candidates presented a lecture on this very topic. The answer is 20, from what I remember. Let’s see if I can dig up a cite. > > from [this page](http://www2.edc.org/makingmath/mathprojects/gameOfSet/set_results.asp) \*\* Oh man, this is great. I’ll need to digest all of this tomorrow. Thanks. ---
**Author:** ![biqu](https://avatars.discourse-cdn.com/v4/letter/b/7feea3/32.png) [@biqu](https://boards.straightdope.com/u/biqu)\ **Post date:** [July 4, 2003, 1:11am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/11 "2003-07-04T01:11:36Z")
To answer the question as worded in the OP: The fewest number of cards for which you could guarantee a set is 21, of course – one more than the maximum number of cards in a set-less pile. ---
**Author:** ![Achernar](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@Achernar](https://boards.straightdope.com/u/Achernar)\ **Post date:** [July 4, 2003, 1:33am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/12 "2003-07-04T01:33:26Z")
Right, well, since this problem has been done (great link, BTW), how about the more general case? Say you have a deck of n[sup]m[/sup] cards, each of which is unique, each with n attributes having m possible values. What is f(n, m), the size of the largest hand which does not have a set of n cards which either all match or all differ in each of its m attributes? f(3, 4) = 20, we’ve seen. I can also contribute f(1, m) = 0 and f(n, 1) = n - 1. 😃 Also, using **Hubajube** ’s method, we know that f(n, m) \>= (n-1)[sup]m[/sup]. ---
**Author:** ![Hubajube](https://avatars.discourse-cdn.com/v4/letter/h/c37758/32.png) [@Hubajube](https://boards.straightdope.com/u/Hubajube)\ **Post date:** [July 4, 2003, 1:34am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/13 "2003-07-04T01:34:16Z")
OK, I couldn’t wait even though I need to get some sleep. I read the cites, and I see where my answer was flawed. For the 3-category case, I didn’t see the 9 setless cards as given here: [http://setgame.com/images/matrix7.gif](http://setgame.com/images/matrix7.gif) I thought that a 2x2x2=8 corner cube represented the maximum. That’s why I thought 16 was the maximum for the 4-category case. Thanks again, amore. ---
**Author:** ![Tyrrell\_McAllister](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/tyrrell_mcallister/32/16772_2.png) [@Tyrrell\_McAllister](https://boards.straightdope.com/u/Tyrrell_McAllister)\ **Post date:** [July 4, 2003, 3:56am UTC](https://boards.straightdope.com/t/math-question-the-game-set/186147/14 "2003-07-04T03:56:22Z")
**Hubajube** , you might want to send an email to one of the mathematicians [Diane Maclagan](http://math.stanford.edu/~maclagan/) or [Benjamin Lent Davis](http://www.math.psu.edu/bdavis/). They have written a paper called “The Card Game SET”, which is to appear in The Mathematical Intelligencer, volume 25, number 3, 2003. Perhaps they would send you a PDF of their paper. If not, you could track down the reference in a university library when it is published. I have read a preprint, and much of it is quite readable, even if you don’t know much math. And perhaps the parts you don’t understand will encourage you to learn the relevant math.