The Power of Child's Play Please Register or Log in to view the hidden image! Akshat Rathi↱ brings the buzz: 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. It's a children's game. Simple and straightforward, or so we might presume. 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.) It's actually a quaint setup, compared to what comes next: 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. So it goes, the essence is to transform the cap set question into a geometry problem. To the one, this is apparently where the fun begins. To the other, I'm not a mathematician and thus cannot explain it to you. Which is why it's good that the preprint for Croot, Lev, and Pach is posted to arXiv↱. Meanwhile, it's one thing to complain mathematicians can't leave well enough alone; it's a children's game, for heaven's sake. But the proper retort would seem to be that this is what happens when the mathematicians don't leave well enough alone, and, you know, why complain? Turns out Set is fun for grown-ups, too. ____________________ Notes: Croot, Ernie, Vsevolod Lev and Peter Pach. "Progression-free sets in Z_4^n are exponentially small". Preprint. 5 May 2016. arXiv.org. 5 June 2016. http://bit.ly/1stKGhG Rathi, Akshat. "The simple math that helped mathematicians solve a vexing problem in the kids' card game 'Set'". Quartz. 2 June 2016. QZ.com. 5 June 2016. http://bit.ly/1O9stQi
