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.) 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?
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
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?
Yes. The deck is 3x3x3x3=81 cards.
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.
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.
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.
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
Exactly.
Oh man, this is great. I’ll need to digest all of this tomorrow. Thanks.
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.
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].
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
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.
Hubajube, you might want to send an email to one of the mathematicians Diane Maclagan or Benjamin Lent Davis. 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.