# David Madore's WebLog: On the game of Set

(Monday)

## On the game of Set

Strange: I thought I had mentioned this game on this blog somewhere before, but I can't find trace of it. So let me say something of it. It is played with a deck of 81 cards, all unique, each card displaying one, two or three identical symbols (of three possible kinds) in one of tree possible colors and one of three possible shadings (unshaded, shaded or solid filled). So all the 3×3×3×3=81 combinations of symbol count, shape, color and shading (each of the four parameters having three possible values) are represented exactly once on the deck. Now we say that three cards from the deck form a set when each of the four parameters (count, shape, color and shading) is either identical over the three cards or different on all three (for example, for three cards to form a set, it is necessary for them to all display the same count of symbols, which can be either one, two, or three, or else for one card to display one symbol, another one two, and the third card three; and similarly—and independently—for shape, color and shading). For the benefit of mathematicians, we can say things more concisely: the deck is the four-dimensional affine space over the finite field with three elements, and a “set” is simply an affine line in this space; and mathematicians will quickly compute that there are 1080 possible sets among the 81 cards (with each card belonging to exactly 40 different sets).

However, this is not so much a game of mathematics as one of observation: essentially, the goal is to quickly spot a set in a given array of randomly dealt cards. So, for example, the image on the left shows twelve cards (perhaps not quite identical to the ones found in the commercial card game, because I have created my own images, but this hardly matters; here, the three shapes are rectangles, ovals and butterflies—or whatever you wish to call them—and the three colors are red, green and blue), among which there is one—and only one—set: can you see it? It can be quite tricky (I'm not sure how difficult this particular one is: now that I know where it is, it simply leaps to my eye so obviously that I can't imagine how anyone could miss it, but I have spent entire minutes vainly looking for a set in a given array of cards, so I know how frustrating it gets): while mathematically all kinds of sets are equivalent, they appear very different to the brain, and some are much easier to spot than others (I guess the greater the number of parameters which are equal over the set, the easier the set is to locate—except possibly symbol count which had better be different because “one two three” is easier to find than “two two two”). As a teaser for the visual cortex (mine is notably defective), this game is really mind-boggling.

One possible way to play this game among friends is to shuffle the deck, deal out twelve cards in a rectangular array, and wait until someone cries set, at which point he must promptly remove the three cards he found and replace them with new ones from the deck; if someone calls a set in error, he is forbidden to speak again until someone else calls one correctly. If all players agree that no set is to be found (which is rare, but not impossible: around 97% of all collections of twelve cards have at least one set in them), replace three arbitrary cards with new ones, or perhaps add three new ones. At the end of the deck, the winner is the player who spotted the greatest number of sets.

Incidentally, one can (well, a mathematician might, at least) ask for the largest possible number of cards that does not contain a set. It is fairly easy to find sixteen cards not containing a set (how?), and the best estimate I could find (with a fairly easy reasoning) in the other direction was that thirty-seven cards always contain a set; actually, it turns out that one can find twenty cards without a set (although doing so takes some cleverness), and that any collection of twenty-one cards always contains a set: the proof of these assertion can be found in a paper by Benjamin Lent Davis and Diane Maclagan.

I have written a little program (using GTK+) with which one can play Set (en solitaire, however: one simply has an indefinite amount of time to find the set and click on all three cards, at which point they are replaced with new ones and so on until the virtual deck runs out): the shapes in the image shown here are taken from this program (they were designed in PostScript and rasterized using GNU Ghostscript). I'm not sure whether I should distribute this game, however: for one thing, I'm afraid that Set® Entreprises might throw some intellectual property bullshit at me (we live in a world where people fear not the ridicule of patenting something like the four-dimensional affine space over the field with three elements—and most of the time get away with it); for another, the programming style is god-awful, because I did this in two hours whereas I had never used GTK+ before. But if someone insists (especially if that someone is willing to clean the thing up and package it), I might declare my code Public Domain and forget it on an FTP site somewhere.