Set Theory and other Shenanigans by Joel G. '18

Find a Set:

Set is a visual card game. “Sets” in Set consist of 3 cards that, for each of their four characteristics, are either all the same or all different. A set must meet ALL of the following conditions:

• be all the same color or all different colors
• be all the same shape or all different shapes
• be all the same fill or all different fillings
• have all the same number of symbols, or all different numbers of symbols

There is exactly one set in that board of 20 cards. Find it before reading on.

Set is rather popular on my floor, Conner 3. My suite has a card deck that just lives on the lounge table, waiting to catch the eye of unsuspecting psetters to distract them for hours. Sometimes we’ll just play classic games with each other, and other times we’ll get more creative. Recently we invented Memory Set, which is played like Memory, just with 81 cards, sets of 3, and more insanity. It also happens to be impossible.

What also is impossible is the challenge I gave you – there isn’t a single set in the whole board – though I hope you had a merry chase trying to find one. This is incredibly unlikely; boards of 12 rarely don’t have sets, and boards of 15 almost always contain at least one. In fact, 20 is the mathematical limit. I know this because I spent two hours last week finding it, in a coding competition at 3am.

It all started innocently enough, with Jeff ‘18, Matt ‘16, and myself psetting, chatting, and desperately trying to procrastinate. We dealt out some Set cards, but instead started thinking about probability and combinatorics – how many possible sets are there? (1080) What is the average number of sets in a 12-card board? (2.78) How many cards can you have without having any sets? (…)

As it turns out, this was a surprisingly difficult question to answer. None of our preliminary approaches worked, and we couldn’t translate the problem into abstract mathematical ideas like matrices or vectors that we could solve easily. We tried arranging cards ourselves, but the most we could manage was sixteen. Even Colin ‘16, our resident math major, after sitting in silence for 10 minutes, could only give us “an upper bound of 37.”

I’m still not sure whether he made that up or not. Math majors are like that.

From here, we could have given up. We could have chuckled, Googled the answer, and gone back to our work. But instead, the conversation took a distinctively MIT-esque turn:

Matt: “You know… we could brute force this in Python pretty easily.”
Jeff: “Are you sure? I don’t think it’s that simple.”
*tentative pause* *quick glance*
Me: “It’s on. Let’s race.”

And thus the 3am coding competition was born. First we had to set (sorry) up a general interface for dealing with sets: I chose to define a card as a 4-element array of integers between 0 and 2, inclusively, where each index represented a characteristic and each integer represented a specific variant. This way, I could easily check to see if 3 cards made a set using modulus instead of having to nest a ton of “if” statements.

However, I didn’t really have a clue of what to do with the actual algorithm logic. Since there are 81 cards in a deck, it definitely wasn’t feasible to manually check all possible boards: there are over 7×10^13 possible boards with just 12 cards, and we knew that the answer was more than that (although we did have an upper bound of 37). However, Matt found a much more efficient brute-force algorithm (which is not quite an oxymoron) and emerged with the magic number in less than half an hour: 20.

From here, he wrote a translator to convert the meaningless stack of arrays that represented the “winning board” to a list of twenty plain-English card names: “Single Red Hollow Squiggle,” “Triple Green Striped Diamond,” and so forth. We found those cards in our real deck, laid them out on the table, and, lo and behold, there were no sets to be found.

It wasn’t our most productive night ever. But this sort of spontaneity permeates MIT – this is just one example – and I love it. Yes, the routine of “pset, study, repeat” is hard, but the interjections of adventures that seem like they’re just waiting to happen make the academic grind at least partially enjoyable. Plus, we can now nerd snipe Set players!

To me, a brute-force Python script is a sufficiently elegant solution, but others might disagree. If anyone is interested in the deeper mathematics behind why 20 is the answer, you should check out this paper.

Also, if anyone knows somebody who is an avid Set enthusiast, you should find a deck and deal out the board at the top of this post. Then invite them over and nonchalantly tell them that it has exactly one set. Believe me; it’s fun.