5
\$\begingroup\$

Spot It is a card game 55 cards. Each card has exactly 8 symbols on it (though the total number of different symbols used in the 55 card set is 57). For any two cards in the deck, they share exactly one symbol. For example:

4 example spot it cards

What is the algorithm behind building this deck? Intuitively I think there is a formula for creating a deck of N cards, with I symbols per card and using J total symbols.

For the life of me I cannot figure it out.

Can it be done?

\$\endgroup\$
8
  • \$\begingroup\$ This is a graph-theoretical problem and might actually be more on-topic for math.stackexchange.com. \$\endgroup\$
    – Philipp
    Jun 16, 2016 at 22:15
  • \$\begingroup\$ I have no idea how that game is played, but I assume that you also want to make sure the whole set of cards is a single graph and you don't have any "islands" of cards which are connected to each other but not to the rest of the set? \$\endgroup\$
    – Philipp
    Jun 16, 2016 at 22:19
  • \$\begingroup\$ @Philipp Good question about the islands - I hadn't thought about that and do not know what the right answer is. There seem to be several different games one can play with cards like this. \$\endgroup\$
    – fbrereto
    Jun 16, 2016 at 22:32
  • 2
    \$\begingroup\$ you forgot to add that symbols used should be balanced. if not, they could all be connected by the same symbol... \$\endgroup\$
    – Fabricator
    Jun 17, 2016 at 1:14
  • 2
    \$\begingroup\$ Seems this question was asked on math: math.stackexchange.com/questions/36798/… \$\endgroup\$
    – Felsir
    Jun 17, 2016 at 12:26

1 Answer 1

2
\$\begingroup\$

Stand-Up Maths did a great video about this, explaining how you can create a "mono-match" set of cards as points in a finite projective plane.

You can arrange your cards into a square grid with a prime number of rows/columns, and assign shared symbols to all the cards that lie in a line. I've taken a still from the video to draw some of these lines:

Rows

  • Every card in the top row has a shared symbol (the lightning bolt)
    • Every card in the second row has a shared symbol (the anchor)
    • ...and so on for all 7 rows.

Columns

  • Every card in the left column has a shared symbol (the cactus)
    • Every card in the second column has a shard symbol (the treble clef)
    • ...and so on for all 7 columns.

Diagonals

  • Every card along the diagonal from the top-left to bottom-right card has a shared symbol (the car)
    • So does every card following a "down-one, right-one" path starting from the second card (the maple leaf)
    • ...and so on for every one of these down-right 45-degree lines. Note that these lines have to wrap around the square and come back in from the other side.

You can do this for every other diagonal - every pattern of "down one, right X" for some value of X. (In fact, the columns are just the pattern "down one, right zero", and the rows are kind of "down one, right infinity" 😉)

Here's just a couple of lines with "down one, right three", since these get harder to follow in the diagram if we chart them all:

Down one right three

So that gives us \$\left(\text{width of square} + 1\right) = (7+1) = 8\$ sets of lines we can draw through the set, which means 8 symbols per card, one for each of these line slopes. Any two cards we choose must both lie on exactly one of these lines (either in the same row, the same column, or along one of the diagonals with a slope determined by their relative positions in the grid), and so must have exactly one of their 8 symbols in common.

We could stop there and have a playable game of \$\left(\text{width of square}\right)^2 = 7^2= 49\$ cards and \$\left(\text{width of square}\right) \cdot \left(\text{width of square + 1}\right) = 7 \cdot 8 = 56\$ unique symbols. But we can take a step further using projective geometry.

You might notice there's some extra cards sitting outside the grid. 8, in fact, corresponding to the 8 different sets of parallel lines we can draw through the grid. These correspond to the "points at infinity" where those "parallel" lines meet. The top right one is where the horizontal lines along the rows meet, and it has one symbol from every row. The bottom one is where all the vertical lines along the columns meet, and it has one symbol from every column. And so on for the diagonals.

That gives us 7 symbols on each of these cards which must match any given card we pick from the main 7x7 grid. (Every card is in some row or some column or some diagonal with slope m...) But if two of these infinity cards get drawn together, we also need a symbol common to them. So we add one additional symbol, the horizon joining the lines at infinity (the clown face), bringing them up to the same 8 symbols as all the other cards.

That gives us a total of \$\left(\text{width of square}\right)^2 + \left(\text{width of square} + 1\right)= 7^2 + (7+1) = 49 + 8 = 57\$ possible cards, using \$\left(\text{width of square}\right) \cdot \left(\text{width of square} + 1\right) + 1 = 7 \cdot (7+1) + 1 = 7 \cdot 8 + 1 = 56 + 1 = 57\$ unique symbols.

But you note that Spot It only has 55 cards. They left two out, as is mentioned in the Stand-Up Maths video. It's unclear why, but actually removing any number of cards doesn't break the guarantee that any two remaining cards have exactly one symbol in common. It just makes some symbols slightly less frequent than others, which might be of optimization interest if you were to become a highly competitive player. 😉 (For example, it's somewhat safe to look for the snowman last - there are two fewer of that symbol in the version shown in the video)

As mentioned, this construction works for squares whose width is prime - that's the order of the finite projective plane we're using. Keeping it prime ensures any diagonal you pick will only cross each row/column once, so you don't double-up on matched symbols. The video mentions that finite projective planes also exist for orders that are powers of primes, but this construction won't work for them, and you'll need a different technique. (There is an example shown in the video for order 4, if that's of interest) No finite projective planes are known with orders that are not powers of primes, so there you might be out of luck.

But, if you want a number of cards that doesn't neatly fit the \$n^2 + n + 1\$ for prime \$n\$ pattern above, you can always bump up to the next \$n\$ that does let us use this neat construction, and then delete cards until you get down to your target number - trying to keep your deletions roughly balanced between the symbols so you don't unintentionally skew the appearance probabilities too wildly.

He also shows one other way of thinking about this problem, based on what's called a "cyclic difference set". You start by arranging the cards in a circle:

Circular method

If you can find a set of cards to mark with one symbol, so that each possible spacing between them occurs exactly once, then you can place your next symbols by just rotating this set of positions by some number of steps n. The two patterns will then overlap on one and only one card.

Here are the positions to use for differing numbers of symbols per card from the video, though it doesn't give a means to calculate them for other numbers:

Symbols per Card Total Card Count Position offsets
3 7 0, 1, 3
4 13 0, 1, 3, 9
5 21 0, 1, 6, 8, 18
6 31 0, 1, 3, 10, 14, 26
7 N/A No Solution
8 57 0, 1, 3, 13, 32, 36, 43, 52
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .