(continued) I learned this argument from a very nice undergraduate thesis by Saskia Vertregt at TU-Delft in the Netherlands! The use of the word "Planes" should suggest that, at its heart, Set is a game about *geometry*. Cards are points and Sets are lines, which is why, just as Euclid demanded, every two cards determine a unique Set and any two Sets intersect in at most one card.
Okay, 20 is maximal in 4-dimensional set, but you can get an upper bound of 24 pretty easily for a collection with no set (3 collinear points).
First, note that any hyperplane (3-dimensional subspace) with 9 points must contain 4 coplanar points: if not, the 4 planes of that hyperplane containing a pair would have only 4 more points for a total of 6.
If no hyperplane has 9 points, then the whole space is a union of 3 parallel hyperplanes and has at most 8 * 3 = 24 points. If some hyperplane has 9 points, then it contains a plane with 4 points. Now the whole space is a union of the 4 hyperplanes containing that plane, and each can have at most 5 more points (since every hyperplane has at most 9 points, by the 3-set case). That also gives at most 4 + 5 * 4 = 24 points.
First, note that any hyperplane (3-dimensional subspace) with 9 points must contain 4 coplanar points: if not, the 4 planes of that hyperplane containing a pair would have only 4 more points for a total of 6.
If no hyperplane has 9 points, then the whole space is a union of 3 parallel hyperplanes and has at most 8 * 3 = 24 points. If some hyperplane has 9 points, then it contains a plane with 4 points. Now the whole space is a union of the 4 hyperplanes containing that plane, and each can have at most 5 more points (since every hyperplane has at most 9 points, by the 3-set case). That also gives at most 4 + 5 * 4 = 24 points.
(continued)
Remarkably, the argument can be done in just a couple of pages: it's rare that a hard (or seemingly hard!) problem turns out to have such a short solution.
To give a small taste of the difficulties, here's an explanation for why you can't have 10 cards in 3-dimensional Set without a Set. If a,b,c are three cards which don't form a Set, we define the "Plane" of (a,b,c) as follows. Throw in the card that forms a set with ab, the card that forms a set with ac, and the card that forms a set with bc. Now you have 6 cards. Once again add every card that forms a set with two cards you already have. This time there's a lot of repeats, and you end up with 9 cards; this set of nine cards is what we call a Plane. (One example of a Plane is the set of all 9 red cards.) You can check that:
a) every pair of cards is contained in exactly 4 Planes;
b) Any five cards in a Plane must contain a Set.
Now suppose you have 10 cards. Plainly there is some color which appears on at most 3 cards; without loss of generality, say that's red. Then there are at least 7 non-red cards, and at least 2 red cards. Let a and b be two red cards. There are 4 Planes containing a and b; the red Plane and three multicolored ones. Each the 7 non-red cards is contained in one of the 3 multicolored Planes; so one of the multicolored Planes contains at least 3 non-red cards, + the two red cards, so it contains 5 cards, contradiction.
Remarkably, the argument can be done in just a couple of pages: it's rare that a hard (or seemingly hard!) problem turns out to have such a short solution.
To give a small taste of the difficulties, here's an explanation for why you can't have 10 cards in 3-dimensional Set without a Set. If a,b,c are three cards which don't form a Set, we define the "Plane" of (a,b,c) as follows. Throw in the card that forms a set with ab, the card that forms a set with ac, and the card that forms a set with bc. Now you have 6 cards. Once again add every card that forms a set with two cards you already have. This time there's a lot of repeats, and you end up with 9 cards; this set of nine cards is what we call a Plane. (One example of a Plane is the set of all 9 red cards.) You can check that:
a) every pair of cards is contained in exactly 4 Planes;
b) Any five cards in a Plane must contain a Set.
Now suppose you have 10 cards. Plainly there is some color which appears on at most 3 cards; without loss of generality, say that's red. Then there are at least 7 non-red cards, and at least 2 red cards. Let a and b be two red cards. There are 4 Planes containing a and b; the red Plane and three multicolored ones. Each the 7 non-red cards is contained in one of the 3 multicolored Planes; so one of the multicolored Planes contains at least 3 non-red cards, + the two red cards, so it contains 5 cards, contradiction.
Thank you, professor! And congratulations on landing a big one!
Great work on the problem! Several people found a 9-card configuration, and indeed, one can't do any better. In regular 4-dimensional set, the most cards you can have without a Set is 20. This result has been rediscovered by many people over the years; Marcia Falco, the inventor of Set, told me it was known as far back as the 70s by exhaustive computer calculation. The largest 5-dimensional configuation with no Set has 45 cards, and in 6 dimensions the maximum is 112.
So what's the general formula? Here's the thing: we have no idea. We don't even know the answer in 7 dimensions! These problems are shockingly hard. The maximality of 112 in 6-dimensional set was proved by Aaron Potechin, in 2008, and it took 16 pages.
Still, we try. In n-dimensional Set, there are 3^n cards. Write f(n) for the maximal number of cards you can have on the table without a Set. Understanding this function f(n) as best we can is a famous old problem, which Terry Tao once called "perhaps my favorite open question":
https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-...
For a long time, we knew very little about how large f(n) could be. For instance, we had no upper bound of the form f(n) < x^n for any x less than 3. That changed this summer! Work of Ernie Coot, Vsevolod Lev, Peter Pach, Dion Gisjwijt, and myself showed that f(n) was at most (2.756)^n.
https://arxiv.org/abs/1605.09223
So what's the general formula? Here's the thing: we have no idea. We don't even know the answer in 7 dimensions! These problems are shockingly hard. The maximality of 112 in 6-dimensional set was proved by Aaron Potechin, in 2008, and it took 16 pages.
Still, we try. In n-dimensional Set, there are 3^n cards. Write f(n) for the maximal number of cards you can have on the table without a Set. Understanding this function f(n) as best we can is a famous old problem, which Terry Tao once called "perhaps my favorite open question":
https://terrytao.wordpress.com/2007/02/23/open-question-best-bounds-for-...
For a long time, we knew very little about how large f(n) could be. For instance, we had no upper bound of the form f(n) < x^n for any x less than 3. That changed this summer! Work of Ernie Coot, Vsevolod Lev, Peter Pach, Dion Gisjwijt, and myself showed that f(n) was at most (2.756)^n.
https://arxiv.org/abs/1605.09223
A slight variant of the question might be easier to analyze because, with this variant, we will not have to special-case the requirement that a legal triplet always has at least one attribute where the instances are all different. (That is, if all attributes are three-of-a-kind in the original problem then it is not a legal triplet because it is not three distinct cards.)
If we shuffle many decks together then we allow the possibility of having two or more copies of a given card. Furthermore, adding a second copy of a card to a subset of the cards that does not already have a legal triplet will not create a legal triplet. That is, a best solution to the multi-deck game has twice as many cards as a best solution to the one-deck game; simply duplicate each card of the latter.
Is this variant easier to solve, e.g., via inclusion-exclusion?
If we shuffle many decks together then we allow the possibility of having two or more copies of a given card. Furthermore, adding a second copy of a card to a subset of the cards that does not already have a legal triplet will not create a legal triplet. That is, a best solution to the multi-deck game has twice as many cards as a best solution to the one-deck game; simply duplicate each card of the latter.
Is this variant easier to solve, e.g., via inclusion-exclusion?
It's very tiring to see the "registered" R in a circle next to every instance of the noun SET referring to the game. And totally unnecessary from the standpoints of the law, New York Times style, and graceful writing.
2
For 4 dimensions I don't think I have much of a chance at proving a maximum, but computationally I have found up to 20-membered SET-free collections. Here's one (using Morgan's symbolism):
POS1
ROS1
RDS1
PSS1
POE1
ROE1
RSE1
GSE1
PST1
PSS2
GOE2
POS3
ROS3
RSS3
GSS3
GOE3
RDE3
RSE3
GSE3
GOT3
The algorithm:
Do the following a bunch of times:
Start with a full deck D.
For each card c:
For each difference d:
If both c+d and c+2d are in D:
If coin flip is Heads:
Remove c+d.
If tails:
Remove c+2d.
If D is bigger than the saved deck, if any:
D becomes the saved deck.
Print the the cards in the saved deck.
POS1
ROS1
RDS1
PSS1
POE1
ROE1
RSE1
GSE1
PST1
PSS2
GOE2
POS3
ROS3
RSS3
GSS3
GOE3
RDE3
RSE3
GSE3
GOT3
The algorithm:
Do the following a bunch of times:
Start with a full deck D.
For each card c:
For each difference d:
If both c+d and c+2d are in D:
If coin flip is Heads:
Remove c+d.
If tails:
Remove c+2d.
If D is bigger than the saved deck, if any:
D becomes the saved deck.
Print the the cards in the saved deck.
1
First we prove that the game with 2 features has SET-free collections of at most 4 cards. Code the cards as pairs of coordinates, each from 0 to 2, forming a 3x3 grid.
The all-same SETS are obviously visualizable as tic-tac-toe lines in the grid. But the all-different ones are also viewable that way: the diagonals, obviously, but also the ones that contain a corner and two mid-side nodes. Think of the grid as repeated identically on all sides (or think of it as a "wrapping" space); then these SETS are also co-linear.
For instance, one wrapping line starts with the top-center node; going down one and right one gets us to the center-right node; from there, down one and right one gets us to the lower-left corner node. These three nodes form a SET all-different in the column feature. Each node is on four lines in all, with slopes characterizable by the differences between points: points in rows have difference (1,0), columns (0,1), diagonals and wrapping lines (1,1), and (1,-1), and each SET corresponds to a line containing three nodes. Each node is on a line with each other node, the other eight nodes breaking down into the four lines, reflecting the fact that any two cards form a SET with exactly one third card (their "triplet").
((continued in a reply))
The all-same SETS are obviously visualizable as tic-tac-toe lines in the grid. But the all-different ones are also viewable that way: the diagonals, obviously, but also the ones that contain a corner and two mid-side nodes. Think of the grid as repeated identically on all sides (or think of it as a "wrapping" space); then these SETS are also co-linear.
For instance, one wrapping line starts with the top-center node; going down one and right one gets us to the center-right node; from there, down one and right one gets us to the lower-left corner node. These three nodes form a SET all-different in the column feature. Each node is on four lines in all, with slopes characterizable by the differences between points: points in rows have difference (1,0), columns (0,1), diagonals and wrapping lines (1,1), and (1,-1), and each SET corresponds to a line containing three nodes. Each node is on a line with each other node, the other eight nodes breaking down into the four lines, reflecting the fact that any two cards form a SET with exactly one third card (their "triplet").
((continued in a reply))
Suppose we have a SET-free collection of 5 cards; then, five nodes in the grid are occupied, no row with three occupied nodes. So the rows contain 2, 2, and 1 occupied nodes. The occupied node in the 1-row is on that line (the row) plus three others that contain no other points in that row. Those three lines contain all 6 of the points in the 2-rows, and at most two of them can contain one of the two unoccupied nodes in those rows. Therefore at least one of the lines forms a SET. So the maximum size of a SET-free 2x2 collection is 4.
Now consider the three-feature case, coded as triples of coordinates from 0 to 2, forming a 3 dimensional 3x3x3 grid of 27 points, each corresponding to a card. A collection of cards is represented by occupied points in the grid. Once again each card forms a SET with every other card and each pair has a unique triplet. And once again the SETs correspond to lines, each node now being on 13 lines.
((continued in one more reply))
Now consider the three-feature case, coded as triples of coordinates from 0 to 2, forming a 3 dimensional 3x3x3 grid of 27 points, each corresponding to a card. A collection of cards is represented by occupied points in the grid. Once again each card forms a SET with every other card and each pair has a unique triplet. And once again the SETs correspond to lines, each node now being on 13 lines.
((continued in one more reply))
By reasoning similar to the 2x2 case, every pair of nodes is on the same plane as every other node, with each such plane containing the third point they are co-linear with and six of the other nodes, so each pair is on four planes in total. Each such plane is subject to our 2-dimensional result that if it is SET-free it contains no more than 4 occupied nodes, because a three occupied points on any such plane, like any straight line, will either be parallel to a given axis (all-different as to the features that axis represents), perpendicular (all-same) or diagonal (all-different) to it.
Suppose we have a SET-free collection of 10 cards, i.e., 10 occupied nodes. Break the grid down into 3 layers, each with 3 rows and 3 columns. By the 2x2 case reasoning, no layer can have more than 4 occupied nodes, so either one layer has 2 or 2 layers have 3. Choose one of the lonliest layers and pick 2 nodes on it. They are on four planes that contain all the other 8 occupied nodes. One of them, the lonely layer itself, contains either 0 or 1 occupied nodes, so the remaining three contain at least seven in addition to our two nodes. But then one must contain at least 5, and so we do not have a SET-free collection. Thus the maximum, witnessed by Morgan's example below, is 9.
Suppose we have a SET-free collection of 10 cards, i.e., 10 occupied nodes. Break the grid down into 3 layers, each with 3 rows and 3 columns. By the 2x2 case reasoning, no layer can have more than 4 occupied nodes, so either one layer has 2 or 2 layers have 3. Choose one of the lonliest layers and pick 2 nodes on it. They are on four planes that contain all the other 8 occupied nodes. One of them, the lonely layer itself, contains either 0 or 1 occupied nodes, so the remaining three contain at least seven in addition to our two nodes. But then one must contain at least 5, and so we do not have a SET-free collection. Thus the maximum, witnessed by Morgan's example below, is 9.
I have a solution for a related problem that I am posting in case it helps us with the current problem. Suppose I deal three cards off the top of the deck and they make a legal set. How many possible ways can this happen? For the color attribute the three cards must be all red, all green, all purple, or be, in dealt order, one of the 6 permutations of {red, green, purple}. That is a total of 9 possibilities for the color attribute. If there are A attribute types (e.g., A=3 or A=4 in the posted problems), there are 9^A possibilities for the dealt cards. Well, almost, because 3^A of the 9^A possibilities do not use any permutations and thus would make the three dealt cards be identical. So there are 9^A−3^A possibilities.
When we do not care about the order that the three cards come off the top of the deck, we have to divide this by 6. The number of possible legal sets is thus (9^A – 3^A) / 6. When the number of attribute types is A=1, 2, …, 6 the number of possible legal sets is 1, 12, 117, 1080, 9801, 88452. (And that happens to be http://oeis.org/A016142, hmm…)
When we do not care about the order that the three cards come off the top of the deck, we have to divide this by 6. The number of possible legal sets is thus (9^A – 3^A) / 6. When the number of attribute types is A=1, 2, …, 6 the number of possible legal sets is 1, 12, 117, 1080, 9801, 88452. (And that happens to be http://oeis.org/A016142, hmm…)
Consider any one of the (9^A – 3^A) / 6 three-card legal sets. The three cards in the set will be included in a set of N randomly chosen cards with probability (N / 3^A) × ((N−1) / (3^A – 1)) × ((N−2) / (3^A – 2)). So a randomly chosen set of N cards will have on average (9^A – 3^A) / 6 × (N / 3^A) × ((N−1) / (3^A – 1)) × ((N−2) / (3^A – 2)) legal triplets in it.
When A=3, the values for N=3, …, 27 are 0.04, 0.16, 0.40, 0.80, 1.40, 2.24, 3.36, 4.80, 6.60, 8.80, 11.44, 14.56, 18.20, 22.40, 27.20, 32.64, 38.76, 45.60, 53.20, 61.60, 70.84, 80.96, 92.00, 104.00, 117.00. For example, 8 randomly chosen cards will have 2.24 legal triplets (possibly overlapping) on average.
When A=4, the values for N=3, …, 27 are approximately 0.01, 0.05, 0.13, 0.25, 0.44, 0.71, 1.06, 1.52, 2.09, 2.78, 3.62, 4.61, 5.76, 7.09, 8.61, 10.33, 12.27, 14.43, 16.84, 19.49, 22.42, 25.62, 29.11, 32.91, 37.03. For example, 16 randomly chosen cards will have 7.08860759 legal triplets on average.
When A=2 the values for N=3, …, 9 are approximately 0.14, 0.57, 1.43, 2.86, 5.00, 8.00, 12.00.
When A=3, the values for N=3, …, 27 are 0.04, 0.16, 0.40, 0.80, 1.40, 2.24, 3.36, 4.80, 6.60, 8.80, 11.44, 14.56, 18.20, 22.40, 27.20, 32.64, 38.76, 45.60, 53.20, 61.60, 70.84, 80.96, 92.00, 104.00, 117.00. For example, 8 randomly chosen cards will have 2.24 legal triplets (possibly overlapping) on average.
When A=4, the values for N=3, …, 27 are approximately 0.01, 0.05, 0.13, 0.25, 0.44, 0.71, 1.06, 1.52, 2.09, 2.78, 3.62, 4.61, 5.76, 7.09, 8.61, 10.33, 12.27, 14.43, 16.84, 19.49, 22.42, 25.62, 29.11, 32.91, 37.03. For example, 16 randomly chosen cards will have 7.08860759 legal triplets on average.
When A=2 the values for N=3, …, 9 are approximately 0.14, 0.57, 1.43, 2.86, 5.00, 8.00, 12.00.
There are 9 of any type (shape, color or number) amongst the 27 cards. Since drawing 5 of a type (color or shape or number) will mean drawing in the best case scenario of 2 of sub-type; 2 of another sub-type and 1 of the third sub-type, thus completing a set. So the maximum we can have of any type from the 9 is 4. We can thus get two 4s of two types. Now from the third type, whatever we draw will complete the set.
For the four attributes scenario, of color, shading, number and shape, there are
3 variations in each and hence the total number of unique cards = 3^4 = 81
The maximum number of cards you can draw without making a set is 16. This way you can avoid the third in each attribute and thus make a set impossible.
For the four attributes scenario, of color, shading, number and shape, there are
3 variations in each and hence the total number of unique cards = 3^4 = 81
The maximum number of cards you can draw without making a set is 16. This way you can avoid the third in each attribute and thus make a set impossible.
Now I am certain that we can improve on 16 as the maximum number of cards without a legal set. Here is a 17 member group. Read as s. no., color, shading (hollow, dark or shaded) and number
1 P H Di 1
2 G D Cy 2
3 P H Di 2
4 G H Di 2
5 G D Cy 1
6 G H Di 1
7 P H Cy 2
8 P D Di 1
9 G D Di 1
10 G D Di 2
11 G H Cy 2
12 P H Cy 1
13 P D Cy 2
14 P D Cy 1
15 G H Cy 1
16 P D Di 2
17 R D Cy 2
1 P H Di 1
2 G D Cy 2
3 P H Di 2
4 G H Di 2
5 G D Cy 1
6 G H Di 1
7 P H Cy 2
8 P D Di 1
9 G D Di 1
10 G D Di 2
11 G H Cy 2
12 P H Cy 1
13 P D Cy 2
14 P D Cy 1
15 G H Cy 1
16 P D Di 2
17 R D Cy 2
It seems hard to check a specific example and maybe even harder to prove for all examples (if true) that the examples are the same up to "permutation."
By permutation I mean swapping, for example, red for green, or swapping the color attribute for the shape attribute. That would give ((3!)^3)*(3!) permutations.
By permutation I mean swapping, for example, red for green, or swapping the color attribute for the shape attribute. That would give ((3!)^3)*(3!) permutations.
2
My 11-year-old found 9:
3-G-Oval
3-P-Oval
3-R-Diamond
2-R-Diamond
2-R-Oval
2-P-Oval
2-P-Squiggle
1-G-Diamond
1-R-Squiggle
3-G-Oval
3-P-Oval
3-R-Diamond
2-R-Diamond
2-R-Oval
2-P-Oval
2-P-Squiggle
1-G-Diamond
1-R-Squiggle
1
This is not a valid 9 because there is a set here as follows:
1-R-Squiggle
2-R-Oval
3-R-Diamond
As you can see the three are of the same color but different shapes and different numbers.
1-R-Squiggle
2-R-Oval
3-R-Diamond
As you can see the three are of the same color but different shapes and different numbers.
Thank you. Back to the deck!
There is a nine combination. Nomenclature is (number)(color)(shape).
3PS, 2PS, 1PD
3GS, 2GS, 1GD
3RD, 2RD, 1RO
3PS, 2PS, 1PD
3GS, 2GS, 1GD
3RD, 2RD, 1RO
This seems to work and proves my answers wrong. Back to the board to see if 9 is the maximum.
The best for the three attributes cards is 8. One would see that the 8 cards do not have a shape (squiggles), a color (purple) and a number (three). Any card addition will have to necessarily involve one of these 3 missing attributes and would therefore create a set.