How many sets can you find in 12 cards? They find 14, but leave open a proof of optimality.
Discussion of finding many cards with no set, and other misc questions.
Generic upper bound: for k cards, choose 2, assume they have a 3rd that completes the Set. This triple-count Sets, so we get an upper bound of (k choose 2) / 3. When k is congruent to 2 mod 3, this is not an integer, so round down in those cases.
For k = 3^d, the generic upper bound is achieved by any affine subspace of dimension d. In fact, this is the only way to achieve the generic upper bound: such a set of cards is closed under the negasum operation, which is equivalent to being an affine subspace. So when k is not a power of 3 and is not congruent to 2 mod 3, we may decrement the generic upper bound by 1.
Update 2012-06-26: Another refinement to the generic upper bound applies to even values of k. In this case, when considering a single point, the other cards of Sets it makes are disjoint pairs. Thus, it lies in at most floor((k-1)/2) Sets. Summing over all points to triple-count Sets, this gives an upper bound of floor((k-1)/2)*k/3, which is an improvement for even k.
Theoretically-resolved values of k are indicated by light green. Values resolved by integer programming are indicated by light blue.
| k | Lower Bound | Generic UB | Refined UB | IP Optimal |
|---|---|---|---|---|
| 3 | 1 (LBAFF) | 1 | ||
| 4 | 1 (LB4) | 1 | ||
| 5 | 2 (LB5) | 3 | 2 (UB5) | |
| 6 | 3 (LB6) | 4 | 3 (UB6) | |
| 7 | 5 (LB7) | 6 | 5 (IP7) | |
| 8 | 8 (LB8) | 8 | ||
| 9 | 12 (LBAFF) | 12 | ||
| 10 | 12 (LB10) | 13 | 12 (IP10) | |
| 11 | 13 (LB11) | 18 | 13 (IP11) | |
| 12 | 14 (LB12) | 20 | 14 (IP12) | |
| 13 | 25 | 16 (IP13) | ||
| 25 | 92 (IP25) | |||
| 26 | 104 (IP26) | |||
| 27 | 117 (LBAFF) | 117 | ||
| 81 | 1080 (LBAFF) | 1080 | ||
(LBAFF): Achieved by any affine subspace.
(LB5): Two 1-dimensional affine subspaces intersecting at a point.
(LB6): Example: (0000, 0001, 0002, 0010, 0020, 0022).
(LB7): Take any 9 cards that have 12 Sets (an affine subspance), and remove two cards. Removing the first card destroys 4 Sets. Removing the second card destroys 3 Sets.
(LB8): Take any 9 cards that have 12 Sets, and remove one card. Each card was in 4 Sets, because 4*9/3 = 12. Since each card was in 4 Sets, 8 Sets remain after deleting a card.
(LB10): Take 9 cards with 12 Sets, then add any card.
(LB11): Take 9 cards with 12 Sets, then add any card p. Select any card x from the first 9, and let q = -(p+x). Since p was not a member of the affien subspace, neither is q, so we may also add q to the board to get 13 Sets.
(LB12): Example: (0000, 0001, ..., 0022, 0100, 0200, 0202).
(UB4): Assume at least one Set is present. It is a 1-dimensional affine subspace, having three cards. The fourth card cannot be a member of that affine subspace, and hence is not a negasum of any two previous cards, and thus not a member of any Set. This gives an upper bound of 1.
(UB5): Assume at least two Sets are present. They must intersect at a single point (since distinct 1-dimensional affine subspaces only intersect at a single point). Any other Set would need to intersect one of the previous two in at least two points, which is impossible, giving an upper bound of 2.
(UB6): Assume at least two Sets are present. Again, they must intersect at a single point. Relabel the common point to zero, so that those two Sets are linear subspaces. Let p be the sixth point, which lies outside both the two original Sets. Suppose for contradiction that there are four Sets present in total, so that p is a member of two Sets. Both of these two p-Sets must intersect each original Set in exactly one point, which hence is not the zero point. So WLOG by change of basis, the two p-Sets are {0001, 0010, p=0022} and {0002, 0020, p=0011}, giving two contradictory values for p. Thus, 3 is an upper bound.
(IP7): Near-instantaneous.
(IP10): Near-instantaneous.
(IP11): ~20 seconds.
(IP12): Around 3 minutes of computation by CPLEX on an IP tweaked to take advantage of symmetries in the problem.
(IP13): Around 21 minutes computation.
(IP25): ~5 minutes.
(IP26): ~1 second.
Lemma: If among the 12 cards there are 9 cards that have 12 Sets, then the 12 cards have at most 14 Sets.
Proof sketch: For those 9 cards to have 12 Sets, they must be an affine subspace. Call it W.
Consider the three other cards: a, b, c. If abc is a Set, then the 12 cards would only have 13 Sets altogether. So we may assume abc is not a Set. Since none of a,b,c can be elements of W, and since W is closed under negasum, they can only participate in Sets that involve two of a,b,c and one point of W. This limits the possible number of Sets to 15.
Now, suppose there really are 15 Sets. Write the sets involving a,b,c as abx, acy, bcz, where x,y,z are points in W. Using a+b+x=0, a+c+y=0, b+c+z=0, we derive the formulas a=x+y-z, b=x+z-y, c=y+z-x. These are affine combinations, which shows a,b,c are in W, a contradiction.
Lemma: If among the 12 cards there are 8 cards of affine dimension 2, then the 12 cards have at most 14 Sets.
Proof sketch: Suppose otherwise, so there are at least 15 Sets present. Then the 9th card to complete the affine subspace W must be missing, by the previous lemma.
Consider the other 4 cards. Each must be part of at most 3 Sets, since any Set it is a member of can only intersect W in one point. But then, any could be deleted and replaced by the missing point of W to increase the number of Sets, since the missing point completes 4 Sets. This is a contradiction.
Lemma: If among the 12 cards there are 7 cards of affine dimension 2, then the 12 cards have at most 14 Sets.
Proof sketch: Let the affine subspace in question be W. Note that adding one missing point of W would complete 3 Sets in W, and then adding the remaining missing point would complete 4 Sets in W, for a total of 7.
On the other hand, consider the 5 non-W points. Removing one would destroy at most 4 Sets, and removing another would destroy at most 3 Sets.
Thus, we may complete W without decreasing the number of Sets, so this reduces to the first Lemma.
(Thanks to Simon Parent for asking about this.)
Adding more dimensions would not help for k=12. IP experiments indicate that if the solution is forced to have affine dimension 4, then only 13 Sets are possible, in contrast to the 14 that are possible with affine dimension 3.
(Thanks for Simon Parent for suggesting and discussing this direction.)
Maximizing the number of Sets in k cards is equivalent to minimizing the number of Sets lying fully outside those k cards.
Call the chosen points "red points" and the other points "blue points." Let n_rb denote the number of Sets with r red points and b blue points. The total number of Sets breaks into four categories:
(1/3)(n choose 2) = n_30 + n_21 + n_12 + n_03
= n_30 + ((k choose 2) - 3n_30) + (((n-k) choose 2) - 3n_03) + n_03
n_30 + n_03 = (1/2)((k choose 2) + ((n-k) choose 2)) - (1/6)(n choose 2)
Therefore, maximizing n_30 is the same as minimizing n_03.