# The Unapologetic Mathematician

## Set — the card game

I’d like to talk about the card game Set. Why? Because the goal is to find affine lines! Huh?

Well, first you have to understand that we’re not working over the usual fields we draw our intuition from. We’re using the field $\mathbb{Z}_3$ of integers modulo $3$. A bit more explicitly, we start with the ring $\mathbb{Z}$ of integers and quotient out by the ideal $3\mathbb{Z}$ of multiples of $3$. This is a maximal ideal, because if we add in any other integer we can subtract off the closest multiple of $3$. Then we’re left with either ${1}$ or $-1$, and this gives us all the integers in our expanded ideal. But we know that the quotient of a ring by a maximal ideal is a field! Thus adding and multiplying integers modulo $3$ gives us a field. For the three elements of $\mathbb{Z}_3$ we’ll use $\{1,2,3\}$ (using $3$ instead of the usual ${0}$).

So what does this have to do with the card game? Well, each one has four features, each picked from three choices:

• Colors: red, green, or purple
• Symbols: squiggles, diamonds, or ovals
• Patterns: solid, striped, or outlined
• Numbers: one, two, or three

Let’s consider the color alone for now. We choose (somewhat arbitrarily) to correlate the colors red, green, and blue with the elements ${1}$, $2$, and $3$ of $\mathbb{Z}_3$, respectively. We don’t want to think of them as “being” the field elements, nor even as the elements of a one-dimensional vector space over $\mathbb{Z}_3$. The arbitrariness of our correspondence points to the fact that the colors constitute an affine line over $\mathbb{Z}_3$!

Similarly, we have lines for symbols, patterns, and numbers. And it’s pretty straightforward to see that we can take the product these affine lines to get a four-dimensional affine space. That is, the cards in Set form an affine four-space over $\mathbb{Z}_3$, and this is the stage on which we play our game.

Now what’s the goal of the game? You have to identify a collection of three cards so that in each of the four characteristics they’re all the same or all different. What I assert is that these conditions identify affine lines in the affine four-space. So what’s an affine line in this context?

Well, first let’s move from the affine four-space of cards to the affine four-space of four-tuples of field elements. We’ll just use the lists of choices above and identify them with ${1}$, $2$, and $3$, respectively, and read them in the same order as above. That is, the four-tuple $\left(3,1,2,2\right)$ would mean the card with two purple, striped squiggles. We can do this because (since they’re torsors) all affine spaces of the same dimension over the same field are isomorphic (but not canonically so!).

Now we can say that an affine line is a map from the standard affine line (given by “one-tuples” of field elements) to this affine four-space. But it can’t be just any function. It has to preserve relative differences! Since we have only three points to consider, we can reduce this question somewhat: an affine line is a list of three four-tuples of field elements, and the difference from the first to the second must equal the difference from the second to the third.

So we can take any two points, and then we can work out what the third one has to be from there. And we can tell that each of the four components works independently from all the others. So let’s look at colors alone again. Let’s say that the first two cards have colors $c_1$ and $c_2$. Then the affine condition says that $c_3-c_2=c_2-c_1$. That is, $c_3=2c_2-c_1$. It’s straightforward from here to see that if $c_1=c_2$, then $c_3$ is again the same as those two. On the other hand, if $c_1$ and $c_2$ are different, then $c_3$ must be the remaining choice.

What have we seen here? If we start with two cards with the same color, the third card on the affine line will have the same color as well. If the first two cards have different colors, the third one will be the remaining color. And the same analysis applies to symbols, patterns, and numbers. Thus affine lines are sets of three cards which are all the same or all different in each of the four characteristics.

Now that we know that, what can we do with it? Well, look at the gameplay. We don’t have all of the cards spread out at once: we deal out a certain number at a time. So the question is: how many points in the affine space $\mathbb{Z}_3^4$ can we take without them containing an affine line? This is analogous to the problem of placing eight queens on a chessboard. A more advanced problem is to give the expected number of affine lines in a subset of size $n$.

Advertisements

July 17, 2008 Posted by | Algebra, Linear Algebra | 18 Comments