Math Circle Problem: Analysis of the Game “Spot it!”

This problem was originally posed by Sue on her blog Math Mama Writes (and was presented by her at the Match Circle Institute). There’s a kids’ game called Spot It, where there are cards with pictures all over them in a pile. If you have a match with the pile in the middle, you call out the name of that icon and grab the card. The person who collects the most cards win.

But here’s the interesting part – despite there being 57 different pictures and 55 different cards, every card has one and only one match with every single other card.

How did they make this game?
Would it work for every number of pictures?
Is there an algorithm for every number of pictures?

The best way to see why this is such an interesting question is by trying to make your own deck with 3, 4, 5, 6 etc different pictures on each card. If you do that, my “solution” below might make some sense!

.
.
.
.
.

.
.
.
.
.
(scroll for discussion of solution)
.
.
.
.
.

.
.
.
.
.
(scroll for discussion of solution)
.
.
.
.
.

.
.
.
.
.
(scroll for discussion of solution)
.
.
.
.

.
.
.
.
.
.

Now, I know people have solved parts of this problem, but I’m not sure I’ve seen a full solution yet. Another teacher and I set about making our own deck with 4 pictures on each card. Here is what we did:

First, if you have 4 pictures on each card, and each picture appears 4 times, this means that you need 13 different symbols and 13 cards. Why? If you used ABCD on the first card, this means A must appear three more times. But B, C and D can’t appear on any of those other three cards, otherwise they would have more than one match. So the next card is AEFG. Using similar arguments, this means you need six more symbols to make the other two cards with A on them. AHIJ, AKLM. That’s a total of 13 symbols, so if they all appear 4 times (and there are 4 pictures on a card) that must mean there are 13 total cards. For n cards, you need n*(n-1)+1 cards… (try to prove that, and see if you can see a discrepancy with this and the number of cards in an actual spot it deck).

Now, B must appear three more times, so we labeled three more cards B. B needs to have a match (but only one match!) to the 4 original cards we created, so what we for each of the three cards was to take the letter in the same position on each card. So, for example, the card on the far right has B, and then the letter in the top right position on each remaining card. The next card has B and the letters in the bottom left etc. Using that, we’re done our B’s (and are more than halfway through our deck!).

C also needs to appear three more times, so we put C at the top left of each card. We can’t use the same exact algorithm that we did for the B cards because otherwise the C cards would have many matches with the B cards. Instead, after we put C, we went back to the A cards and for the three remaining cards, we grabbed a letter and jumped forward a position. So for the first card, we put C in the top left, then took the letter from the top right on AEFG, the letter from the bottom left of AHIJ and the letter from the bottom right of AKLM. This made new groupings of the non-ABCD letters. Then, we made the D cards similarly, but instead of jumping forward a position, we jumped back.

This gave us 13 cards, and the game worked!

But then we tried out our algorithm to make a game with 5 pictures on each card (so 21 pictures/cards). And it didn’t work. So we tried it again with 6 pictures on each card (31 pictures/cards)… and it DID work. Why?

Well, the one with 5 symbols didn’t work because when we were distributing the letters, we were permuting a group of 4 remaining positions. So after making the “B” card that has all the symbols in a certain position, we made the “D” card where the symbols come from jumping forward two spots. But jumping forward two spots twice gets you back to the original spot, which means we were making cards which included more than one match.

So thinking about what we were doing, we were actually just doing modular arithmetic with the remaining symbols on a card. For the example with 4 symbols, we were left to permute 3 positions, which means essentially we were in mod class 3. If you labeled the spots [1], [2] and [3] (or [0]), then we were starting with a certain spot, like [0], and then adding a certain number (my language is really sloppy, I apologize). So the first B card are positions from [1] + [0] repeatedly, the second B card is from [2] + [0], and the third B card is from [3] + [0]. The first C card are positions from [1] + [1] repeatedly, the second C card is from [2] + [1], the third C card is from [3] + [1] repeatedly.

Of course, this doesn’t work at all if you are in mod 4. [1] + [2] = [3], then [3] + [2] = [5] = [1]. So you get back to your original position, which can’t work because you already have a card with positions from [1] + [0] on them.

So when does this work? When the positions you are permuting are a prime number (abstract algebra, never thought you would arise in my life!). Which means that our method only works for p + 1 pictures, where p is a prime. But theoretically, that should work for any number one larger than a prime, and the algorithm could easily be programmed into a computer to construct these cards.

Satisfied? I’m not.

So that’s certainly a solution, but it’s messy. And it’s incomplete, because it doesn’t work for 5 pictures. We thought that might mean that it’s not possible to make a deck with 5 pictures on a card, but a student at the institute did that very thing using trial and error. So is there an algorithm that does work for all numbers?

(By the way, apparently the solution has something to do with Finite Field Planes. I have no idea what that is, but a bunch of people posted more sophisticated solutions on Sue’s blog. I just wanted to detail my experience with this problem to show that there’s a lot you can do with just a little bit of experimentation, and a lot of connections you can make from the experimentations to deep mathematics. A perfect Math Circle Problem.)

Advertisements

Posted on July 15, 2012, in Math Circle and tagged , , , . Bookmark the permalink. 13 Comments.

  1. Thanks for writing this up! I should too, but I haven’t had the energy yet.

    I made a deck of 5-picture cards while on the plane back to California. I used my algorithm, which sounds a lot like yours. And it worked. I’m too tired to dig them out right now, but I’ll try to post more tomorrow. (I also started on a deck of 7-picture cards, but didn’t finish it yet. I got the impression those might be a problem even if the 5’s weren’t.)

  2. Hmm, I’ll have to find what I did on the plane because now I agree with you that our procedure doesn’t work for decks with 5 symbols per card. I’d also like to look at the deck made by that student… (This comment prompted by email to me from someone in Indonesia, asking about the solution.)

  3. This card game just came to my attention and I too was attracted to the mathematical possibilities. I considered some of the basics, e.g the principle that all the other symbols on a set of cards sharing a given symbol must be unique, but then I “looked it up on the internet” and found this very nice discussion. I didn’t see why the cyclic permutations should have special status even though they work nicely for P+1 symbols per card, with P prime.

    I did work out the solution for 5 cards, following the pattern suggested here. I was casting around without too much luck when I hit on what seemed to be the key: that every pair must appear among 3 sets of 4 foursomes formed from {F,G,H,I} X { J,K,L,M } X { N,O,P,Q } X { R,S,T,U }, and appended to {C,D,E} ( again, following the discussion given here. )

    This means that when forming the indexes of each foursome, we must use 12 AND 21, 23 AND 32, etc., so we require 1234, 2134, etc.

    we get

    1234
    2143
    3412
    4321

    which appended to {C} gives

    CFKPU
    CGJQT
    CHMNS
    CILOR

    and {D,E} are handled by a cyclic permuation of the last three columns. I checked it out with awk and “sort -u”

  4. I recently came across the SPOT IT! card game, and was of course interested right away in the math implications. I thought about it while then “looked it up on the internet” and found this blog. I got interested in the case of 5 symbols because I didn’t see why the cyclic permuations should be a necessity. I hit on the idea that after forming the A and B cards, as above, then moving on to { C,D,E } X { F,G,H,I } X { J,K,L,M } X { N,O,P,Q } X { R,S,T,U }, the indexes of the last four sets had to contain 12 AND 21 as well as 23 AND 32, etc. so the set for C is given by:

    1234
    2143
    3412
    4321

    CFKPU
    CGJQT
    CHMNS
    CILOR

    and D and E are obtained from a cuclic permutation of the last 3 columns. I checked it out with awk and “sort -u” to see that all C(21,2) = 84 symbol pairings are uniquely present on the 21 cards with 5 symbols each.

  5. Thank you, pfathinatin. I am trying to write this up per the request of someone who is posting background on all the math circles done at the Join Math Meetings in January. I still hadn’t really settled the question of 5 pictures per card yet. I will read this more carefully when I have time.

  6. Another simple way to figure out the max number of cards is to use one common number and count up with the others. There is a lot of math, but it works out the same as when you do it as follows:

    1,2,3,4
    1,5,6,7
    1,8,9,10
    1,11,12,13

    The number of rows is the number of symbols per card. The highest number of symbols is the number of possible cards, so 13 cards are possible.

  7. This month’s IBM Research’s challenge (http://domino.research.ibm.com/Comm/wwwr_ponder.nsf/Challenges/June2014.html) is about a similar problem.

  8. Thanks for this great post – and indeed thanks to all who have written on this. For completeness, I wanted to point out that the accepted answer at http://math.stackexchange.com/questions/36798/what-is-the-math-behind-the-game-spot-it notes that if p is a prime *power* (such as 2^2=4) then the algorithm should still work, though you would have to be careful to work in the correct field.

    • Sorry for being cryptic, as I see I have been – the above means that the constructions for 5 symbols per card are fine, but that this is why they are quite different.

  1. Pingback: Spot it! … a combinatoric cornucopia | Lew's Garage

  2. Pingback: I made a Spot-it Clone – Aaron Barker

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: