morriswalters - Yeah, I think you misinterpreted things originally but hopefully that's cleared up now. There is some finite set of symbols. Each card in the deck is an unordered set of D of those symbols. Every symbol is a member of an equal number of cards as every other symbol. Every pair of cards shares *exactly* one symbol (e.g. they also share at least one symbol). What are the possible sizes of deck that can be constructed?
Naturally, this has been asked on stackoverflow before. On one side math behind it
and on the other construction of the cards
The magical concept used is finite projective planes
and I won't pretend to really understand it, but it seems to work. Like David said above, for n+1 symbols per card you can have up to n^2+n+1 cards, at least if n is a prime power. No idea about the upper bound of points when n is not a prime power –whether a projective plane exists for such an order is an open problem, but someone may have estimated the maximum number of cards for n+1 number of symbols per card.
The nice thing about it is that you can remove any* number of cards (or points in the plane) and the game still works –for example there are 57 cards possible for Spot It!, but they only used 55.
*you'd have to remove all cards containing a certain symbol (i.e. all points on a line) to keep the additional restriction of "all symbols must occur equally often".
Since 6 is the smallest non prime power, can we make a
deck with 7 symbols per card, all symbols occuring evenly? It can't be constructed from a projective plane (since no projective plane of order 6 nor 10 exists according to wikipedia), but maybe some other construction is possible.
Nice, thanks for the links! Yeah, once I started drawing graphs and trying to come up with explicit constructions, the kinds of graphs I was getting started to look like projectivey things. It looks like projective planes are great for generating classes of solutions, but I'm not sure that this gets you all the solutions. I'll need to take a closer look at those links, but a cursory skimming of them doesn't immediately reveal an easy way to proceed on that particular front.So, here's what I can work out:
Let D be the number of symbols per card, let C be the number of cards, let R be the number of repeats of each symbol(how many cards each symbol appears on), let S be the number of distinct symbols. We get some obvious and trivial solution classes when some of these are zero, so ignore those cases and assume all of these values are strictly positive.
- There are two ways of counting total instances of symbols, either cards * symbols per card = CD, or symbols * repeats of each symbol = SR. Therefore, CD = SR.
- Considering a single card in the deck. It has D unique symbols, and each of them occurs R times, so R-1 times on other cards. All such D(R-1) of these occurrences of these symbols on other cards must be disjoint, else we would have a pair of cards sharing more than one symbol. And this must be all other cards in the deck, else we would have a pair of cards having no common symbols. Therefore, C = 1 + D(R-1).
- Substituting in to CD = SR, and doing some basic algebra, we can get to R(D^2-S) = D(D-1). Since everything is an integer, R must be a factor of D(D-1).
- Consider all S(S-1)/2 pairs of distinct symbols. Any such pair can occur on at most one card, because if a pair occurred on more than one card, those two cards would share both of those symbols in common. Since every card has D(D-1)/2 distinct pairs of symbols,
we have the constraint that CD(D-1)/2 <= S(S-1)/2. With some basic algebra I believe this simplifies to (D-1)(R-D)(R-1) <= 0. This implies that R <= D, unless D = 1. And in the latter case, any size deck is possible (all cards have just the same single symbol), so that case is trivial and so setting those aside we get further that D >= 2 and R <= D.
So to summarize, excluding trivial and vacuous solutions, it seems that for any D >= 2 the potentially-possible deck sizes are of the form:
C = 1 + D(R-1)
where R is a factor of D(D-1) within the range [1,D].
So then we can build a little table of potentially-possible deck sizes:
For D = 2: 1(R=1), 3(R=2)
For D = 3: 1(R=1), 4(R=2), 7(R=3)
For D = 4: 1(R=1), 5(R=2), 9(R=3), 13(R=4)
For D = 5: 1(R=1), 6(R=2), 16(R=4), 21(R=5)
For D = 6: 1(R=1), 7(R=2), 13(R=3), 25(R=5), 31(R=6)
For D = 7: 1(R=1), 8(R=2), 15(R=3), 36(R=6), 43(R=7)
For D = 8: 1(R=1), 9(R=2), 25(R=4), 49(R=7), 57(R=8)
However, while all of these are potentially-possible given the conditions above, I don't know whether they are actually possible, or whether it turns out that there are other problems that can arise when attempting to actually construct a deck of that size.
Clearly all the cases where R=1 are possible - single card deck where the single card has D symbols. And R=2 is always possible - just use the "complete graph" construction that multiple people in this thread have mentioned.
I think that the projective plane constructions from Flumble's links shows that all the cases in the above table where R=D are possible whenever D is a prime power plus one. By excluding all points on a single projective line, I think we can also get that all the cases where R=D-1 are possible when D is a prime power plus one, although I haven't thought through that carefully to make sure.
But there are a lot of cases remaining. Is it possible to construct decks for the R=D and R=D-1 cases in the above table when D is one more than a number that isn't a prime power? Such as (D=7, R=6, 36 cards) or (D=7, R=7, 43 cards). And how about the intermediate cases, like (D=6, R=3, 13 cards), or (D=7, R=3, 15 cards)? I haven't tried yet to manually construct decks for these cases.
Curious to see if anyone else can come up with constructions for some of these cases, or if anyone sees any additional general solution classes or any additional constraints that can be used to rule out some more of the possibilities in that table.
That's about where I'm at now!