Games provide structure. And this is a particular kind of structure because the structure of a game often leads to creative thought. It’s a casual environment where the mind can wander. Set is a particularly famous game amongst mathematicians. If you were a mathematics major in undergraduate, then you probably came in contact with Set.
The premise of set is simple, identify a set of 3 cards where all the cards either share a particular attribute or differ on that attribute. There are four such attributes in Set: color, shape, shading and number. Usually the game is played with 12 face-up cards. And usually there are multiple sets within those 12 cards. But sometimes there isn’t a set in those 12 cards and when that happens 3 more card are added until a set is found.
This simple game provides endless opportunities for combinatorial proofs for new and seasoned mathematicians. There are easy proofs: Prove why there are no sets among these 12 cards. And there are hard proofs: How many cards can be added to the table and there are still no sets? That is: Identify the largest number of cards which can potentially have no sets.
This last question plagued mathematicians for a long time. And it came from playing with this game! Well, if I’m being honest, the question didn’t come from the game. The problem equivalent to “the smallest collection of cards containing 4 attributes with no set” was solved in 1971. The game Set wasn’t created until 1974. In fact, mathematicians were worried about this problem long before the game was developed. But the game, so easy a 6 year old can play, introduces many new ideas about combinatorics to new mathematical thinkers. And since I’m being honest, this is a game where the youngest player at the table generally wins.
But that’s beside the point! The point is that we solved it! …Well, not quite! But, we came up with a better upper bound. Which is pretty awesome. For a collection of cards, we can give a much improved bound on how many cards are needed to guarantee the existence of a set. Previously, for decks larger than 200 cards, we could only bound the number of cards needed at 0.5% of the deck. Now we know it’s only 0.0000043% of the deck.
The coolest part is the way this proof was solved. I’m not going to in the details, the folks at Quant Magazine and Gower’s Weblog do a great job of that. But, suffice to say, even Terence Tao called the proof “sort of magical.” Mathematicians are currently rushing to use the techniques from this proof to prove other things. Which is one of the coolest parts about math. It’s abstract enough that a new technique can be applied in lots of areas. One example is using the technique to improve things like matrix multiplication– which has very little to do with a card game built around finding sets of similar attributes.