When I was introduced to the game Set, with its 81 cards bearing colored shapes, it seemed so simple to understand that a child could win it. And yet it was not easy to win.
At the heart of the game is a decades-old puzzle that mathematicians were similarly befuddled by—until last month, when a new solution using simple math emerged. Since then, in a series of papers published in the past few weeks, mathematicians around the world have discussed the prospect of using the solution to work on other hard problems.
First, here’s how Set works: The game’s 81 cards are distinguished by four attributes: color, shape, shading, and number (each with three variations). To win a “set,” players have to find three cards that all display the same attribute or none of the same attributes. For instance, the image above is a set, because none of the cards share any attribute. The person with the most sets at the end of play wins.
Now here’s the puzzle: To start the game, 12 cards are laid out and players search for a set. If they don’t find one, which can happen in rare cases, three more cards are laid out, and so on. So, mathematicians wondered, what is the largest number of cards where no solution can be found? The answer, proved in 1971, was 20. (The trademarked card game Set was created in 1990, after it was invented in 1974 by a geneticist who came up with it while matching the genetic traits of epileptic German Shepherd dogs.)
Mathematicians wondered, why should we stop at cards with only four attributes? What if there were cards with 100 attributes on them, what would then be the largest collection of cards that would contain no “set”? That number of attributes is so large that not even the fastest computer in the world can calculate all the permutations and combinations needed to find the answer. The only way to solve it would be to find a mathematical proof. So this became known as the “cap set problem,” and it has bothered mathematicians for decades because its solution eluded them.
One early solution to the cap set problem was that, for a deck of x cards with n attributes, the maximum number of cards with at least one set would be x/n. This works in the case of the actual game of Set, where for 81 cards with 4 attributes, the maximum number of cards with at at least one set is 81/4 ≈ 21. But this solution wasn’t easily generalized for higher number of attributes, and mathematicians suspected there to be a better solution.
On May 5, three mathematicians stunned the field by publishing a solution to the cap set problem using the polynomial method. This powerful method has emerged in the past decade, but it is simple enough that universities are introducing them in undergrad classes.
The new solution is not easy to explain in non-technical terms, but here’s a somewhat oversimplified summary: The mathematicians converted the cap set problem into a geometry problem, which the polynomial method is adept to handle. To do that, each attribute was converted into a dimension, creating an n-dimensional problem. With this and some math trickery, the mathematicians found the best generalized solution so far. Depending on the number of attributes, it turns out that the maximum number of cards with at least one set could be as big as the deck of cards itself.
This approach to the problem doesn’t affect the game of Set, but its elegance and simplicity has mathematicians in a tizzy. They are now working hard to find ways to use this solution for other problems. And it could have an impact beyond card games and mathematical theory: Even if such problems are solved just for the sheer curiosity, they can in the future lead to discoveries and inventions that have real-life applications.
“The fact that the cap set problem finally yielded to such a simple technique is humbling,” Jordan Ellenberg, a mathematician at the University of Wisconsin, Madison told Quanta Magazine. “It makes you wonder what else is actually easy.”