Set™ Theory Part III
Oh, goody-more Set!
For a moment I thought I’d discovered something beautiful and profound about Set, but it turns out I was off by a small but rapidly increasing amount. While working this out, I found out some other neat things about the game by accident. (To avoid repeating myself too much I’ll assume that you’ve read my previous two posts about the game.)
If you’ve played much Set, you probably know the Fundamental Theorem of Set, even if you weren’t aware of it:
Theorem. Given any two cards in the Set deck, there is exactly one card that can be added to complete a SET.
I, and others before me, have previously explained some useful implications of the Fundamental Theorem. I started thinking about how the theorem might be applied to figure out how many SETs a given number of cards could contain.
By definition, three cards are required to make a SET, and obviously, three cards can contain only one SET. Can you make two SETs from four cards?
The Fundamental Theorem implies that we can’t find a group of four cards that will form two SETs. Consider cards A, B, C and D. If {A, B, C} is a SET, there is no way to include D in a SET without using two of A, B, C-and we know that any two of A, B, C can only make a SET with the third member of that group. If you’re a visual person, like me, it may make more sense to try to graph the four cards on the 3×3×3×3 “magic square” hypercube (in which any tic-tac-toe is a SET). Wherever you put the fourth card, e.g.,
A B C
. D .
. . .you’ll find you can’t make a second tic-tac-toe with the fourth card. (Because “wraparound” tic-tac-toes are allowed, the SET {A, B, C} shown is equivalent to any other SET in the hypercube.)
What is the probability that four randomly drawn cards will contain one SET? We know already that the full deck contains 1,080 SETs. Each of them may be paired with any other single card in the deck-78 of them-to create a total of 78 × 1,080 = 84,240 four-card combinations with a SET. The total number of four-card combinations, with or without a SET, is (81 × 80 × 79 × 78)/24 = 1,663,740. Thus, the chance of drawing four cards with a SET is 84,240/1,663,740 = 4/79 = 1 in 19.75, or about 0.0506.
How about 5 cards? Two SETs are certainly possible,
A B C
D . .
E . .but what about three? Again, Theorem 1 prevents us from making three SETs. The first two SETs in a group of five cards will share exactly one member, like this: {A, B, {C}, D , E}. There is no way of selecting cards for a third SET without including either two from {A, B, C} or two from {C, D, E}.
Calculating probabilities of drawing one or two SETs in a group of five random cards sounds too much like work, so I won’t attempt it. I do, however, have the energy to tell my computer to simulate a bunch of random five-card deals and count up the SETs in each. In 10,000 randomly selected groups of 5 cards, 8,754 had no SETs, 1227 had one and 19 had two. The probability of drawing five cards containing two SETs is, then, very roughly 1 in 500.
With six cards things start to get interesting. It’s easy to see that three SETs are possible in six cards:
A B C
D E .
F . .How about four? Can we select three cards, such that no two are already in the same SET? Yes, B, D and E-but these don’t form a SET. It’s easiest to see why in the diagram above. The six cards form a triangle. We can make the three sets differ by more than two attributes, which corresponds by adding more dimensions, like this (in three dimensions):
A . . . B . . . C
D . . . E . . . .
F . . . . . . . .but it’s still a triangle, which is inherently a two-dimensional figure. (In other words, we can think of a combination of six cards using a single tic-tac-toe grid “without loss of generality,” as they say in the biz.) Because we can exchange rows and columns, configurations like
A B C
. D E
F . .and
A B C
D . .
E F .are also equivalent.
Finding a distribution of numbers of SETs starts to get really tough when we consider six cards. In 100,000 random draws of six cards,
76,353 had no SET,
22,008 had one,
1,610 had two, and only
29 had three.
Seven? Did someone say “seven”? Now we can start exploring higher-dimensional arrangements of cards, but after some thought I realized that staying in two dimensions will still give the configuration with the most SETs. The reason is that we need to reuse cards as much as possible, and that is achieved best by keeping the cards in as few dimensions as possible in SET-space. The combination here contains five SETs. Four are obvious-one row, two columns and the diagonal {C, E, F}-but there is also a fifth, the “wraparound” diagonal {C, D, G}.
A B C
D E .
F G .I can’t see any way to get more than five SETs from seven cards.
Eight cards is actually an easier configuration to parse than seven. Here, we have eight SETs: two rows, two columns, one diagonal, one wraparound diagonal with slope 1 ({A, F, H}) and two wraparound diagonals with slope -1 ({B, F, G} and {C, D, H}). If you try moving the “hole” in the 3 × 3 grid to any other position, no matter where it is, you’ll find you have two row SETs, two columns, and four diagonals (at least some of which will be wraparound-if the hole is in the center, all will be wraparound).
A B C
D E F
G H .To recap: In groups of 3, 4, 5, 6, 7 and 8 Set cards, there are a maximum possible 1, 1, 2, 3, 5 and 8 SETs, respectively. Now where have I seen that sequence before? Oh yeah-the Fibonacci sequence! The Fibonacci numbers have many nifty properties, arguably the neatest of which is that the ratio of successive Fibonacci numbers approaches the golden ratio,
φ = [sqrt(5) + 1]/2 ~ 1.618.
I would never have guessed they would show up in Set, as well.
Does this sequence continue? Let’s look at a group of nine cards. Now the 3 × 3 matrix is fully occupied, and we have a total of 12 SETs-three rows, three columns, three diagonals with slope 1 (including two wraparound) and three diagonals with slope -1 (ditto). Because this is such an important group, here is a diagram of real cards:
Oh, dear-we’ve fallen 1 short of the next Fibonacci number, 13. I’m quite sure, however, that 12 is the largest number of possible SETs in nine cards. The group of nine cards shown is saturated with SETs, in the sense that any two cards within the group of nine can be paired with a third card, also within the group of nine, to make a SET. (This situation is akin to the mathematical notion of a “group.”) Thus, the Fundamental Theorem holds for this subsection of the Set deck; or, in other words, this group of cards has all the essential properties of a full deck.
A saturated group of n cards contains (n(n - 1))/6 SETs, which is a generalization of Corollary 1 of the Fundamental Theorem.
Naturally, a group of three cards that forms a SET is also saturated. If we compare the maximum number of SETs in a group of size n with the number in a saturated group of the same size, as in the table below, we see that a collection of nine cards is the next smallest group that can be saturated with SETs. (The corresponding Fibonacci numbers are also included, just for grins.)
No. CardsMax. SetsSat. No. SetsFn - 231114121523.33263537575889.3389121213
Sat. No. Sets, number of sets in saturated group; Fn - 2, the (n - 2)th Fibonacci number.
I propose that only collections of 3, 9, 27 and 81 cards in the deck can be saturated: they could be thought of as complete decks for one-, two-, three- and four-dimensional games of Set. (One could add a fifth dimension, such as three different borders or background colors, for a very challenging game using a 243-card deck.)
We can continue adding cards to our collection, to see how many SETs are possible, right up to 81. You’ve probably already have had as much fun as you can stand looking at groups of Set cards, but I would like to continue up to 12 really quickly, just because 12 is the number of cards dealt out in a standard game of Set.
It seems reasonable to add cards to add cards to our saturated group of nine. Would you agree that no additional SETs can be formed by adding one card to such a group? (Try it.) The situation is analogous to adding a card to a group of three cards that form a SET. Similarly, adding two more cards to our collection of nine can yield, at most, only one more SET, and adding three cards will generate at most two more SETs. In short, groups of 10, 11 and 12 cards can include at most, 12, 13 and 14 SETs, respectively. (I’ll leave it as an exercise for the reader to calculate the probability of dealing 12 random cards from the deck that contain 14 SETs.)
At 9 cards, the saturated number is only 1 less than the seventh Fibonacci number, 13. By the time we reach the entire deck, however, the number of possible SETs falls way behind the Fibonacci sequence: F79, the 79th Fibonacci number, is the incomprehensibly huge number 14,472,334,024,676,220. In contrast, the 81 cards of the full Set deck yield a mere 1,080 SETs, a number smaller by a factor of about 13 trillion.
It is easy to see why the total possible number of sets falls behind the Fibonacci numbers: each entry under “Sat. No. Sets” is (n + 1)/(n + 1) times the previous one, a ratio that approaches 1 as n gets large; whereas the ratio of successive Fibonacci numbers, as mentioned, approaches φ ~ 1.618.*
Oh, well-it was almost a profound revelation.
____________
*While I was doing the calculations for the Fibonacci sequence, I looked at how quickly the ratio of successive Fibonacci numbers approached φ. It turns out that the ratios converge very rapidly: F41/F40 approximates φ to an accuracy of sixteen decimal places!
For a moment I thought I’d discovered something beautiful and profound about Set, but it turns out I was off by a small but rapidly increasing amount. While working this out, I found out some other neat things about the game by accident. (To avoid repeating myself too much I’ll assume that you’ve read my previous two posts about the game.)
If you’ve played much Set, you probably know the Fundamental Theorem of Set, even if you weren’t aware of it:
Theorem. Given any two cards in the Set deck, there is exactly one card that can be added to complete a SET.
I, and others before me, have previously explained some useful implications of the Fundamental Theorem. I started thinking about how the theorem might be applied to figure out how many SETs a given number of cards could contain.
By definition, three cards are required to make a SET, and obviously, three cards can contain only one SET. Can you make two SETs from four cards?
The Fundamental Theorem implies that we can’t find a group of four cards that will form two SETs. Consider cards A, B, C and D. If {A, B, C} is a SET, there is no way to include D in a SET without using two of A, B, C-and we know that any two of A, B, C can only make a SET with the third member of that group. If you’re a visual person, like me, it may make more sense to try to graph the four cards on the 3×3×3×3 “magic square” hypercube (in which any tic-tac-toe is a SET). Wherever you put the fourth card, e.g.,
A B C
. D .
. . .you’ll find you can’t make a second tic-tac-toe with the fourth card. (Because “wraparound” tic-tac-toes are allowed, the SET {A, B, C} shown is equivalent to any other SET in the hypercube.)
What is the probability that four randomly drawn cards will contain one SET? We know already that the full deck contains 1,080 SETs. Each of them may be paired with any other single card in the deck-78 of them-to create a total of 78 × 1,080 = 84,240 four-card combinations with a SET. The total number of four-card combinations, with or without a SET, is (81 × 80 × 79 × 78)/24 = 1,663,740. Thus, the chance of drawing four cards with a SET is 84,240/1,663,740 = 4/79 = 1 in 19.75, or about 0.0506.
How about 5 cards? Two SETs are certainly possible,
A B C
D . .
E . .but what about three? Again, Theorem 1 prevents us from making three SETs. The first two SETs in a group of five cards will share exactly one member, like this: {A, B, {C}, D , E}. There is no way of selecting cards for a third SET without including either two from {A, B, C} or two from {C, D, E}.
Calculating probabilities of drawing one or two SETs in a group of five random cards sounds too much like work, so I won’t attempt it. I do, however, have the energy to tell my computer to simulate a bunch of random five-card deals and count up the SETs in each. In 10,000 randomly selected groups of 5 cards, 8,754 had no SETs, 1227 had one and 19 had two. The probability of drawing five cards containing two SETs is, then, very roughly 1 in 500.
With six cards things start to get interesting. It’s easy to see that three SETs are possible in six cards:
A B C
D E .
F . .How about four? Can we select three cards, such that no two are already in the same SET? Yes, B, D and E-but these don’t form a SET. It’s easiest to see why in the diagram above. The six cards form a triangle. We can make the three sets differ by more than two attributes, which corresponds by adding more dimensions, like this (in three dimensions):
A . . . B . . . C
D . . . E . . . .
F . . . . . . . .but it’s still a triangle, which is inherently a two-dimensional figure. (In other words, we can think of a combination of six cards using a single tic-tac-toe grid “without loss of generality,” as they say in the biz.) Because we can exchange rows and columns, configurations like
A B C
. D E
F . .and
A B C
D . .
E F .are also equivalent.
Finding a distribution of numbers of SETs starts to get really tough when we consider six cards. In 100,000 random draws of six cards,
76,353 had no SET,
22,008 had one,
1,610 had two, and only
29 had three.
Seven? Did someone say “seven”? Now we can start exploring higher-dimensional arrangements of cards, but after some thought I realized that staying in two dimensions will still give the configuration with the most SETs. The reason is that we need to reuse cards as much as possible, and that is achieved best by keeping the cards in as few dimensions as possible in SET-space. The combination here contains five SETs. Four are obvious-one row, two columns and the diagonal {C, E, F}-but there is also a fifth, the “wraparound” diagonal {C, D, G}.
A B C
D E .
F G .I can’t see any way to get more than five SETs from seven cards.
Eight cards is actually an easier configuration to parse than seven. Here, we have eight SETs: two rows, two columns, one diagonal, one wraparound diagonal with slope 1 ({A, F, H}) and two wraparound diagonals with slope -1 ({B, F, G} and {C, D, H}). If you try moving the “hole” in the 3 × 3 grid to any other position, no matter where it is, you’ll find you have two row SETs, two columns, and four diagonals (at least some of which will be wraparound-if the hole is in the center, all will be wraparound).
A B C
D E F
G H .To recap: In groups of 3, 4, 5, 6, 7 and 8 Set cards, there are a maximum possible 1, 1, 2, 3, 5 and 8 SETs, respectively. Now where have I seen that sequence before? Oh yeah-the Fibonacci sequence! The Fibonacci numbers have many nifty properties, arguably the neatest of which is that the ratio of successive Fibonacci numbers approaches the golden ratio,
φ = [sqrt(5) + 1]/2 ~ 1.618.
I would never have guessed they would show up in Set, as well.
Does this sequence continue? Let’s look at a group of nine cards. Now the 3 × 3 matrix is fully occupied, and we have a total of 12 SETs-three rows, three columns, three diagonals with slope 1 (including two wraparound) and three diagonals with slope -1 (ditto). Because this is such an important group, here is a diagram of real cards:
Oh, dear-we’ve fallen 1 short of the next Fibonacci number, 13. I’m quite sure, however, that 12 is the largest number of possible SETs in nine cards. The group of nine cards shown is saturated with SETs, in the sense that any two cards within the group of nine can be paired with a third card, also within the group of nine, to make a SET. (This situation is akin to the mathematical notion of a “group.”) Thus, the Fundamental Theorem holds for this subsection of the Set deck; or, in other words, this group of cards has all the essential properties of a full deck.
A saturated group of n cards contains (n(n - 1))/6 SETs, which is a generalization of Corollary 1 of the Fundamental Theorem.
Naturally, a group of three cards that forms a SET is also saturated. If we compare the maximum number of SETs in a group of size n with the number in a saturated group of the same size, as in the table below, we see that a collection of nine cards is the next smallest group that can be saturated with SETs. (The corresponding Fibonacci numbers are also included, just for grins.)
No. CardsMax. SetsSat. No. SetsFn - 231114121523.33263537575889.3389121213
Sat. No. Sets, number of sets in saturated group; Fn - 2, the (n - 2)th Fibonacci number.
I propose that only collections of 3, 9, 27 and 81 cards in the deck can be saturated: they could be thought of as complete decks for one-, two-, three- and four-dimensional games of Set. (One could add a fifth dimension, such as three different borders or background colors, for a very challenging game using a 243-card deck.)
We can continue adding cards to our collection, to see how many SETs are possible, right up to 81. You’ve probably already have had as much fun as you can stand looking at groups of Set cards, but I would like to continue up to 12 really quickly, just because 12 is the number of cards dealt out in a standard game of Set.
It seems reasonable to add cards to add cards to our saturated group of nine. Would you agree that no additional SETs can be formed by adding one card to such a group? (Try it.) The situation is analogous to adding a card to a group of three cards that form a SET. Similarly, adding two more cards to our collection of nine can yield, at most, only one more SET, and adding three cards will generate at most two more SETs. In short, groups of 10, 11 and 12 cards can include at most, 12, 13 and 14 SETs, respectively. (I’ll leave it as an exercise for the reader to calculate the probability of dealing 12 random cards from the deck that contain 14 SETs.)
At 9 cards, the saturated number is only 1 less than the seventh Fibonacci number, 13. By the time we reach the entire deck, however, the number of possible SETs falls way behind the Fibonacci sequence: F79, the 79th Fibonacci number, is the incomprehensibly huge number 14,472,334,024,676,220. In contrast, the 81 cards of the full Set deck yield a mere 1,080 SETs, a number smaller by a factor of about 13 trillion.
It is easy to see why the total possible number of sets falls behind the Fibonacci numbers: each entry under “Sat. No. Sets” is (n + 1)/(n + 1) times the previous one, a ratio that approaches 1 as n gets large; whereas the ratio of successive Fibonacci numbers, as mentioned, approaches φ ~ 1.618.*
Oh, well-it was almost a profound revelation.
____________
*While I was doing the calculations for the Fibonacci sequence, I looked at how quickly the ratio of successive Fibonacci numbers approached φ. It turns out that the ratios converge very rapidly: F41/F40 approximates φ to an accuracy of sixteen decimal places!