Saturday, June 15, 2013

A "Spot It!" puzzle

The game of “Spot It!” (blueorangegames.com) provided an entertaining mathematical and programming puzzle, which I have mostly (I think) figured out.

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
If we have N=4 then one could imagine cards (A,B), (A,C), (A,D), but then what? You can't go (B,C) because that has nothing in common with (A,D). So bumping N from 3→4 actually reduces the number of cards with M=2.

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 |A B C        
2 |A     D E    
3 |A         F G
4 |  B   D   F  
5 |  B     E   G
6 |    C D     G
7 |    C   E F  
 
1 |A B C D                  
2 |A       E F G            
3 |A             H I J      
4 |A                   K L M
5 |  B     E     H     K    
6 |  B       F     I     L  
7 |  B         G     J     M
8 |    C   E       I       M
9 |    C     F       J K    
10 |    C       G H       L  
11 |      D E         J   L  
12 |      D   F   H         M
13 |      D     G   I   K    
The pattern that seems to emerge from this is that we have
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}
…the total being M(M-1)+1 figures in the alphabet, and M(M-1)+1 cards.

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: