We recently purchased a game called Spot it! f or a young friend of ours. The game consists of a set of cards with eight pictures on each card. If you choose any two cards from the set, exactly one picture will be found on both cards.
Ignoring the degenerate case, what is the largest possible set of cards?
It's not too difficult to establish an upper limit in this problem. Because every pair of cards shares exactly one symbol, we have quite a bit to work with.
Start with any one card, and label the symbols on that card A, B, C, D, E, F, G, and H. The key realization is that the rest of the cards are divided into eight sets (or more generally into n sets, if there are n symbols per card). We can refer to all the cards with symbol A as Set A, all the cards with symbol B as Set B, and so on. Except for the card ABCDEFGH, these sets are disjoint (otherwise the card ABCDEFGH would share at least two symbols with another card). Furthermore, every card belongs to one of these sets (otherwise there would be a card that did not share a symbol with ABCDEFGH). The degenerate case occurs when all the cards are in the same set—for example, each card has symbol A and seven other symbols that are unique to that card.
Consider any card in Set A (other than ABCDEFGH) and call it A1. Now consider the relationship between the eight symbols (or more generally, the n symbols) on card A1 and the cards in Set B. Every card in Set B must contain a symbol from A1. In addition, no two cards in Set B can contain the same symbol from A1 (otherwise those two cards would share B and the common symbol from A1). Since there are eight symbols on card A1, there can only be eight (or more generally, n) cards in Set B, and that's counting ABCDEFGH as one of those eight cards, since A is one of the eight symbols on card A1. Since this argument applies equally to any of the sets A through H, there can only be a maximum of 1 (for ABCDEFGH) + (8 sets) × (7 additional cards per set) = 57 cards in the game. More generally, there can be no more than 1 + n (n − 1) cards in the game if there are n symbols per card.
There is no guarantee that there is a maximal solution of 1 + n (n − 1) cards for every value of n. To show that there is such a set for n = 8, we can construct a solution.
First, let's count the number of symbols in the solution. There are eight symbols on ABCDEFGH, and there are seven other cards in Set A, with seven other symbols on each card. This is 57 symbols, or more generally, n + (n − 1)2 symbols. Note that this is equal to the maximum number of cards for any n, not just for n = 8. We can also see that if there is a full set of 57 cards, then there cannot be more than 57 symbols. If we know the 49 other symbols in Set A, which is seven symbols on each of the seven cards, then we know that one symbol from each card in Set A is on each card in Set B; therefore, there are no symbols in Set B that are not in Set A. No set has more than 57 symbols, and the 57 symbols from Set A are the same 57 symbols in any other set.
We've already started our construction, just by identifying the card ABCDEFGH and the sets A through H. That specifies the placement of the symbols A through H. There are 49 more symbols to place. Let each of the seven cards in Set A (not including ABCDEFGH) correspond to a row in a 7 × 7 matrix, and each symbol on that card occupies one of the columns. By arranging the order of the symbols in each row, we can have the columns of the matrix correspond to the cards in Set B. Is there a way to arrange the symbols on the cards of the other six sets, so that any two cards have exactly one symbol in common?
For n = 8, there is a way to do this. We need to define slices of the matrix (which correspond to the cards) such that any slice (card) intersects any other slice (card) in exactly one element of the matrix (symbol). So far, we've been successful with sets A and B, because each row intersects each column in exactly one element. Any other slices will need exactly one element from each row and one element from each column. The next obvious slice to take is the diagonal, and parallel slices. We can let these correspond to cards in Set C. Card Ci has the symbols Mj,i+j, where the rows and columns of the 7 × 7 matrix are numbered from 0 to 6, and where the array index i+j is understood to mean i + j mod 7.
The next set of array slices must not only intersect each row and each column exactly once, but they must also intersect each of the diagonal slices exactly once. The next most obvious slice to take is a slope of two instead of a slope of one. (I suppose if you think of y as vertical, corresponding to rows and x as horizontal, corresponding to columns, then the slope is 1/2 or −1/2, but that's what I mean by a slope of two.) Card Dj has the symbols Mj,i+2j. Because seven is odd, each of these "slope 2" slices intersects each row, each column and each diagonal ("slope 1") slice exactly once.
Because seven is prime, this generalizes to "slope 3", "slope 4", "slope 5", and "slope 6" slices. In fact, this construction method works for any n = p + 1, where p is prime. That answers the question for n = 8, but what about for other n?
I haven't determined whether or not there is a maximal set of 1 + n (n − 1) cards for arbitrary n. I have demonstrated that there is such a set for n = 2, which is trivial, and also for n = 5, which is not trivial. The cases n = 3, 4, and 6 are all p + 1, so n = 7 is the smallest case that I have not demonstrated.
If you can find a set of 43 cards with seven symbols each, please let me know. Even better, I'd like to hear from you if you can demonstrate that there is no such set for n = 7, or if you can prove that there are (or are not) values of n which cannot have a set of 1 + n (n − 1) cards.
Please send responses toThanks,