Let's talk about the card game SET.
To play, you start with a deck of cards, each of which has a certain number of shapes and different colors and shadings.
You deal out 12 cards and start looking for a set, a collection of three cards that have either all the same or all different patterns.
Now, once you deal out those 12 cards, it's possible that there might not be a set among them.
When that happens, you just deal out three more cards, and in some cases, there still might not be a set, so you can add three more cards.
And this begs the question, what is the maximum number of cards you can deal that might not contain a set?
[MUSIC PLAYING] Before I tell you the answer, let me start by clarifying how the game works.
You have a total of 81 cards, and each card displays an image with four features, shape, color, number, and shading, each of which can vary in three ways.
For example, this card has three green striped diamonds, this card has one purple solid squiggle, and this card has two red outline ovals, and so on.
To start the game, you deal 12 cards face up, and again, the goal is to collect the most sets.
A set is a collection of three cards where either each feature on the cards are all the same or each feature on the cards are all different.
For example, this is a set, because all three cards have the same color, same number of shapes, same shape, and all three cards have different shading.
This is also a set.
All three cards have different colors, different shapes, different numbers of shapes, and different shading.
And here are some other examples of sets.
Now, if your 12 cards don't have a set, then you can keep dishing out cards three at a time until a set is present.
So how many cars does this take?
In other words, what is the maximum number of cards you can deal that might not contain a set?
It turns out the answer is 20, and the proof is pretty involved, but to whet your appetite for the kind of math behind the scenes, let's ask this exact same question but for a lower dimensional version of the game.
That is, let's suppose that the cards only have two instead of four features, like number and shading.
In other words, pick a color, like green, and a shape, like diamond, so only the numbers and shadings will vary.
That means our deck now consists of nine cards.
And we can ask the same question, which I will pose as this week's challenge problem.
Out of these nine cards, what is the maximum number you can deal that might not contain a set?
You can approach the problem in any way you like, but in the next few minutes, let me try to steer you in a geometric direction.
It's a small mathematical detour, but at the end, we'll see how it circles right back to the challenge problem.
OK, here's the detour.
If you watched our video, "How to Divide by Zero," then you're familiar with the quotient set Z mod nZ For example, if n equals 5, then Z mod 5Z is the set of five equivalence classes, 0, 1, 2, 3, 4.
Or if n equals 3, then Z mod 3Z is the set 0, 1, and 2.
They're equivalence classes, but for the rest of the episode, let's just think of them as numbers.
And you know that we can do arithmetic with these numbers.
For instance, here's the multiplication table for Z mod 3Z times Z mod 3Z.
0 times anything is always 0.
1 times 1 is 1, and 2 times 2 is 4, which is 1 mod 3 and so on.
OK. Now I want to show you something else.
Let's replace each of the numbers by their original factors.
For example, this 1 is really 1 times 1, so let's replace it with the coordinate 1 comma 1.
Similarly, this 2 is really 1 times 2, so let's replace it by the coordinate 1, 2.
Now do this for all the points.
For each coordinate, the first number is the x, or horizontal component, and the second number is the y, or vertical, component.
So we end up with a three-by-three grid.
This grid is called the Cartesian product or Z mod 3Z cross Z mod 3Z, because it's just like the usual Cartesian, or x-y plane that you're used to.
So really, you can think of the Cartesian plane as a kind of multiplication table for real numbers, except instead of considering pairs of real numbers, we are now considering pairs of modulo 3 numbers.
And that's why we get a plane comprised of only nine and not infinitely many points.
Now, what's cool is that we can still do geometry with these nine points.
In particular, we can still make sense of lines in this three-by-three grid.
Remember, a line in the usual Cartesian plane is a collection of points, x, y that satisfy the equation y equals mx plus b, where m, the slope, and b, the y-intercept, are real numbers.
In the exact same way, a line in the grid of nine points is a collection of mod 3 numbers, x and y, that also satisfy the equation y equals mx plus b, where now, m and b are numbers in Z mod 3Z.
For example, these three points comprise the line y equals 2, since the y component of each coordinate is 2.
So here, m is 0, and b is 2.
And this diagonal line has the quation y equals x.
So m is 1 and b is 0, because the x and y components of all three coordinates are equal.
And this line has equation y equals x plus 1.
And this takes a little extra thought.
It doesn't look like a line, so is it really?
Well, the answer is yes if each of the three points satisfies the equation y equals x plus 1.
So do they?
Absolutely.
Look at the point 1, 2.
It's y component, 2, equals it's x component, 1 plus 1.
And that's exactly what it means to say 1, 2 lies on the line y equals x plus 1.
And the same goes for the other two points, therefore, these three points do form a line.
So why doesn't it look like it?
Well, I claim it does.
Notice what happens if we were to expand our grid a little.
Modulo 3, the point 0, 1 is equivalent to 3, 1.
Similarly, 1, 2 is equivalent to 4, 2, and voila, there's our line.
The idea is that once we reduce mod 3, lines simply wrap around the edges.
And this is exactly what happens when forming a quotient like in the Pac-Man universe or a flat torus that Gabe talked about in his episode "Telling Time on a Torus."
OK.
This is all very nice, but it's not just a cute fact.
This is exactly what we need to solve the challenge problem.
Let's recall what it is.
Out of these nine cards, what is the maximum number you can deal that might not contain a set?
OK. How does that relate to geometry?
Remember that the shading of the cards comes in three varieties, solid, striped, and outlined.
Now, think of each option as an element in Z mod 3Z.
For example, let's assign 0 to solid, 1 to striped, and 2 to outlined.
Likewise, there are three different numbers of diamonds, one, two, and three.
So let's assign 0 to three, 1 to two, and 2 to one.
And now, we can encode features of the cards via pairs of numbers, a, b.
The first component represents a shading value, and the second component represents a number value.
For example, this card corresponds to 1, 1 because it has two striped diamonds.
And this card corresponds to 0, 2 because it has one solid diamond.
Do this for each card and we recover our coordinate plane with nine points.
Now, let's think back to what a set is.
A set is a triple of cards, where the shading and number of shapes is either the same or different on all three cards.
For example this forms a set, because the cards have the same number but each has a different shading.
Moreover, this set corresponds to a line, namely, y equals two.
Interestingly enough, the x components all add up to zero, and the y components all add up to zero.
As another example, these three cards also form a set, because the cards have different shading and different numbers.
Moreover, this set corresponds to a line, namely, y equals x.
And interestingly enough, the x components all add up to zero.
And the y components all add up to zero.
And here's one last example, these three cards form a set, because again, their numbers and shadings are all different.
Moreover, this set also corresponds to a line, namely, y equals x plus 1.
And interestingly enough, the x components all add up to zero and so do the y components.
OK.
So it seems like sets correspond to lines in the Z mod 3Z grid, and here's a hint, it's true.
They do.
You can prove it.
Now, can you use that to solve the challenge?
Here it is again.
Among the nine cards, what is the maximum number of them that may not contain a set?
Can you rephrase this question in an equivalent but geometric way and then answer it using the hint?
Once you've got your solution, send it to me in an email at pbsinfiniteseries@gmail.com with the subject line "SET Challenge."
but don't just send me a number.
I want a number and a proof.
Then, we'll select a random winner and send you a T-shirt from PBS Digital Studios.
Good luck, and see you next time.