Saturday, January 21, 2012

Math Adventures: Thinking about Spot it, and Learning Python

My brother lives in Minneapolis, and we visited him last January and this. Both times we used the light-rail train to get to the airport. Last year he had to drop us off pretty early, so we stopped at the Mall of America. We'd arrived too early and most of the stores were still closed, but we wandered around anyway. We found a toy/game store called Marbles - The Brain Store, and I knocked on their doors to ask if I could just come in and browse. They had a good collection of my favorite sorts of toys and games, and they ended up letting me buy a few things, Spot it among them.

It's not a math game at all. It's a contest to see who can find a matching picture first. My son is better at it than I am, so he enjoys winning. Every time I played, I pondered the math question that stared me in the face: How did they make sure every possible pair of cards would have just one match?! But I didn't know how to get started, so I never really pursued the question until recently.

Spot it is a good travel game, so I packed it this year as we headed off to visit family and friends in 4 Michigan cities, a Chicago suburb, and Minneapolis. My old friends Chris and Paul have twin girls my son's age, and our visits to their backwoods home are always a rich experience of outdoor play, good healthy food, and deep conversation. Chris and I decided one evening to look at how Spot it is put together. Chris doesn't think of herself as a mathematician, but she organized the information in a way that helped me solve my problem. It was also a great motivator to think through it together. We used numbers to represent the different pictures, and drew our cards in different layouts, looking for patterns.

We worked on it for a few hours, and got some good insights, but didn't solve it. That was enough to get me hooked. I got my mom to work on it with me. We counted all the pictures, and found 57 different pictures. Then I worked on it on the train to Chicago, and got some good stuff figured out.

One thing I did was to make a mini-version of the game. My 'cards' (circles with numbers in them), used only 4 numbers each. I figured out that I had to use 13 different pictures, and could have a deck of 13 cards - all different. That gave me enough push to find a scheme for the bigger deck. But I wasn't at all sure it was right. There are an awful lot of possible pairs when you have 55 cards. (How many?) How could I be sure I had exactly one match for every pair of cards? I thought I did, but I sure didn't know how to prove it.

That's where I was with the problem when I visited Prairie Creek Community School, about 40 minutes south of Minneapolis. Michelle Martin (who has a chapter in Playing With Math) let me show the kids (4th and 5th graders) the problem, and they all dug in. They pulled out all the cards with a heart - there were 8 - and thought about what they now knew. 8 pictures per card, one of which was the heart, along with 7 others, all different... They decided there had to be at least 57 different pictures (7 unique pictures/card*8 cards + the heart). I liked that they figured that out a better way than I had. The kids worked on the problem so diligently, but had to leave it and go on to other things. (And it didn't occur to me to leave my game there, so they couldn't keep working on it after I left.)

I went back to trying to find ways to prove I had a valid solution. My new burning question was 'Why did Spot it only have 55 cards, when it could have had 57 cards?'  I put my 'cards' on Excel. But I still didn't know how to test each card against each other card. I understand that the macros in Excel use visual Basic, and I hoped I could do something with that, but I was once again pretty stuck.

I asked a colleague to help me get started on the programming, and he recommended Python. I couldn't get started on my own. I found the Python documentation very confusing, and got stuck every step of the way. Yesterday we had a bit over an hour between meetings, and he showed me how to get started with Python. He's learning it too (and he's a computer science teacher). So the best thing he showed me (probably pretty obvious) was to google 'python example x' every time I had a question. This morning I got my program working, and it verified that my method worked!!! Maybe next year I'll generalize this to cards with n pictures on them.

The biggest lesson for me in this adventure was that working with others is a huge motivation for me. But I knew that.



[You may have noticed that I haven't given many details of my solution. I'm hoping you'll all play with it yourselves, of course. If you'd like to discuss all the gory details, please email me at mathanthologyeditor on gmail with your solution ideas.]

20 comments:

  1. At the risk of maybe giving too many spoilers here:

    I spent a lot of time thinking about these cards, too. There's a beautiful card <-> picture symmetry in there somewhere. And it's not a coincidence that there are 7+1 pictures per card, each picture is on 7+1 cards, and there are a total of 7^2+7+1 pictures (and there should be that many cards, too -- which two are missing? I haven't figured that out yet, nor do I have a clue about why they're missing).

    http://en.wikipedia.org/wiki/Projective_plane#Finite_field_planes

    ReplyDelete
  2. I can't wait for you to explain what you found!!!! :)

    ReplyDelete
  3. Thank you, Josh. I had no idea this was connected to 'finite field planes'. Now I'm thinking the stuff Owen was drawing pictures of might be related.

    I emailed the company to ask how they did it and why they left out two cards. I hope they reply.

    Cindy, I wasn't planning on explaining it. If you want to play with it, I'd be happy to give you hints. My solution is pretty complicated, but I bet there's a more elegant way to see it.

    If you're interested in playing with it, one place to begin is to do the mini-version I mentioned, with each card having 4 pictures on it.

    ReplyDelete
  4. I suspect that the reason for the missing cards comes from the cards' production method. Most cards are printed on rectangular sheets, which are then cut into individual cards. So the number of cards in a rectangular sheet needs to have two factors that are neither too large nor too small. Also, you want to be able to make a standard poker deck, which is 54 cards, so the number of cards in a sheet should not be less or much more than that. It appears that 5×11 is a pretty common size, just judging by what I've seen in Magic: the Gathering sets. So it probably just comes down to it being more expensive to make a game with a non-standard number of cards.

    ReplyDelete
  5. I'm also wondering if this deck (with the missing cards) is isomorphic to Ed Pegg's Hoffman-Singleton graph deck, which also has 57 cards.

    ReplyDelete
  6. That's what I love about math. Things that seem entirely different turn out to be the same problem.

    (I don't know if Spot it and the Hoffman-Singleton graph deck are isomorphic, but if they're not, I suppose Spot it will be isomorphic to something else that seems unrelated.)

    ReplyDelete
  7. Oh, I'm dumb. The Hoffman-Singleton thing has only 50 cards, as that page states clearly enough. (I got confused because the next line down from it on the table on the page I linked had a 57 in it, but that's a different graph, and the 57 would not represent the number of vertices/cards for a hypothetical deck based on it. Sorry about that.

    ReplyDelete
  8. There is a whole area in combinatorics called combinatorial design.

    http://en.wikipedia.org/wiki/Combinatorial_design

    I don't remember much about it, but finite geometries are involved.

    In Python, it is easy to over think your programs. It is different than C/C++ in that all of the basic functions you would want are already implemented. You often find that most of the program you're writing is already implemented. Python programmers call it "Guido's Time Machine."

    The first Python program that I wrote required me to rearrange the elements of an array in a random order. I accidently found the shuffle method while learning how to generate random numbers. My program turned into three lines of code.

    ReplyDelete
  9. I had written what I wanted in pseudo-code, so it was mostly learning how to represent and manipulate arrays (more like a list of lists in Python), get file input, and stuff like that.

    I'm happy to send my program to anyone who wants to see it. It doesn't seem like the thing for a blog post, but if folks would like it here, I can do that.

    Yep, that w'pedia article describes the sort of thing I would have done in generalizing this.

    ReplyDelete
  10. >the stuff Owen was drawing pictures of
    >might be related
    some finite projective spaces (e.g.).

    >It's not a math game at all.

    i'm not sure i agreee with you
    100% on your police work...
    here we are, not only *talking
    about* it, but *analyzing* it...
    "why 57?"!

    >This morning I got my program working, and it verified that my method worked!

    pretty exciting. i've long since
    believed that it was half-past-time
    i figured out at least a *little*
    about "python" (for example; other
    freely-available-online programming
    tools, too [of course]). thanks for
    leading the way!

    still. it's the plain-language
    "paper-and-pencil" stuff that
    i long for (& still haven't figured
    out as of now). what's the clearest
    statement of the relevant theorem?
    how is it most easily seen?
    (by a human...?)

    so. i've got my grading *nearly*
    done... let's look at joshua's
    "spoilers".

    ah. yes. N = P^2 + P + 1.
    i know how to make a
    "projective plane" over
    "the field with P elements"
    (or for that matter, the
    field with Q = P^k
    [k \in {1, 2, 3, ...}]
    elements); yes.

    so 7^2+ 7^1 + 7^0 = 57
    qualifies. i've drawn
    this (P^2(F_7)) & even
    run off copies. but it
    was ugly and (as it turns
    out) incorrect.

    anyhow, here's my "projective
    spaces" *category*:
    VK on P^r(F_q).
    .

    almost everything worth knowing
    is understood by considering
    *small examples*.

    MMW rox. V.

    ReplyDelete
  11. I'm still hooked on this. I did a math circle last night on it, and will follow up next Thursday. Turned out we had a very small group. It was exciting to watch pairs and trios, each working on this in their own ways.

    I also got an email from someone in Indonesia recently, wanting the solution. Turns out he's not interested in learning how to think about it. Why would anyone want the solution to this if they don't want to think about it?

    Anyway, I wrote up my procedure, and drew out what goes wrong when there are 5 symbols per card.

    He sent me this pdf. Interesting.

    ReplyDelete
  12. Hello my name is JOE from Australia. My son and I have a loan of a pack and it intrigued us how did this work - only one match with any two cards. So we counted the number of pictures (57) and listed them. then counted by tally the number of each picture - 42 had 8, 14 had 7, 1 had 6. So quickly figured that the one with 6 and the 14 (2 x 7) means that 2 cards were missing - so why are there only 55 cards and published as 55 cards. Is it because 55 is easier to understand than 57? Go me!

    ReplyDelete
  13. Go you, indeed! I'm not sure I ever realized that one of the pictures appears only 6 times. Which one?

    Have you tried figuring out how they managed to arrange the pictures properly?

    ReplyDelete
  14. I'm no math whiz, but i liked reading the analysis trying to figure out how this array of pictures was created. No email esponse from company yet?

    ReplyDelete
  15. "I emailed the company to ask how they did it and why they left out two cards. I hope they reply."

    They did reply (promptly, almost two years ago). They asked me not to share what they said. I figured I should honor their request. I will say that what they said is nothing earth shattering. (It fit our hypotheses above.)

    Anonymous, you don't need to be a math whiz to figure this out, but you do need to be *very* persistent. If you get hooked on thinking about this, you're welcome to email me (mathanthologyeditor on gmail) with any questions.

    ReplyDelete
  16. thanks, becuase i just played the game the first time today, | was more wondering about the missing cards. We theory behind having one match, no more or no less on every card is very interesting. Further, there is a game using 9 cards that has a 3 symbol match. Since i don't own the game (played while visiting relatives) i wonder if the 9 card game only has a single match of 3 symbols or if there are multiple 3 symbol matches. I'm going to go out and buy the game this weekend, and probably the kids simplified version too !

    ReplyDelete
  17. Can you tell me the name of this game with 3 symbols matching? I'd love to look at it.

    ReplyDelete
  18. From Jim - sorry I don't have any online account to sign with.

    My 4 year old granddaughter just got Spot It and I was excited to find this and a couple other discussions going on. I am a bit late getting in on the conversation but I have an algorithm for creating a set of N(N+1)+1 cards for any N prime and a proof that it works. I can't tell whether this is old hat to the readers or not. I can upload it if there is any way to do so. I don't know all the notation being tossed around but I think it's pretty readable.

    I also can't figure out whether anyone has actually seen or generated a set with N not prime.

    ReplyDelete
  19. Your N is one less than the number of pictures on a card, right? Some of the readers here have seen this before. Others, like me, discovered it for the first time through analyzing Spot It. I'm curious about your algorithm. Mine is pretty messy. I think there may be a way to use 5 pictures per card (so N=4), but I'm not sure of that.

    ReplyDelete
  20. Yes you can also generate a set for N = power of prime using projective plane theory (4, 8, 16, 9 27, 25, ...).
    It is more complex than for N prime because calculation needs polynomials.

    It was demonstrated impossible for N=6 mathematically, and for N=10 by brute force search.

    ReplyDelete

 
Math Blog Directory