In case you haven't seen it, there's a deck of some 55 cards; on each card are eight stylized figures of various creatures or things: man, dragon, dog, cat, car, daisy, maple leaf, and so on. Any two cards in the deck have one and only one figure in common: cards 1 and 2 might both have a man, cards 2 and 3 might both have a dragon, but then card 1 won't have a dragon; card 3 won't have a man.
This strikes some people as odd. “Really?” they say. “Any two cards have exactly one thing in common?” It is indeed true. Which of course made me wonder: How does that work? If each card has M figures out of an alphabet of N, how many cards can you have?
Naturally, I started with M=2 and came upon this rather simple set of 3 cards with N=3 symbols:
A | B | |
A | C | |
B | C |
Thus with M=2 there's a sort of optimum value of N, namely 3. What's the optimum value of N for M=3 or M=4? The number of cards might have something to do with the number of combinations of N things taken M at a time, but it doesn't say much about the optimum N for a given M.
After many stabs at this with pencil and paper, I came up with the following lists for M=3 and M=4:
|
|
1. card with figures {1..M} | ||
2. card with figures {1, M+1..2M-1} | (M-1) cards | M sets of (M-1) cards |
… | ||
M. card with figures {1, (M-1)(M-1)+2..M(M-1)+1} | ||
… | ||
(M-1)(M-1)+2. card with figures {M,M+1} and (M-2) figures from the set {2M..M(M-1)+1} | (M-1) cards | |
… | ||
M(M-1)+1. card with figures {M,2M-1} and (M-2) figures from the set {2M..M(M-1)+1} |
I believe the optimal N for a given M is M(M-1)+1; this gives a symmetric (I think) set of cards, with each symbol appearing on M cards. I haven't proven any of this, but I have (of course) written some code that generates a set of these things for the case where M-1 is prime—which is the case for the real Spot It! game (M=8). In particular if M=8 then the optimum N would be 8*7+1=57, and the deck could have 57 cards. Why does the real Spot It! card game have only 55 cards in the deck? You got me.
I'll add a link to the code one of these days but right now I think it's
time for bed.
Update: Code is here
No comments:
Post a Comment