What are the mathematical/computational principles behind this game?

 

My kids have this fun game called Spot It! The game constraints (as best I can describe) are:

  • It is a deck of 55 cards
  • On each card are 8 unique pictures (ie a card can't have 2 of the same picture)
  • Given any 2 cards chosen from the deck, there is 1 and only 1 matching picture .
  • Matching pictures may be scaled differently on different cards but that is only to make the game harder (ie a small tree still matches a larger tree)

    • The principle of the game is: flip over 2 cards and whoever first picks the matching picture gets a point.

    Here's a picture for clarification:

    发现它

    (Example: you can see from the bottom 2 cards above that the matching picture is the green dinosaur. Between the bottom-right and middle-right picture, it's a clown's head.)

    I'm trying to understand the following:

  • What are the minimum number of different pictures required to meet these criteria and how would you determine this?

  • Using pseudocode (or Ruby), how would you generate 55 game cards from an array of N pictures (where N is the minimum number from question 1)?

    • Update:

    Pictures do occur more than twice per deck (contrary to what some have surmised). See this picture of 3 cards, each with a lightning bolt: 3张牌

    Finite Projective Geometries

    The axioms of projective (plane) geometry are slightly different than the Euclidean geometry:

  • Every two points have exactly one line that passes through them (this is the same).
  • Every two lines meet in exactly one point (this is a bit different from Euclid).

    • Now, add "finite" into the soup and you have the question:

    Can we have a geometry with just 2 points? With 3 points? With 4? With 7?

    There are still open questions regarding this problem but we do know this:

  • If there are geometries with Q points, then Q = n^2 + n + 1 and n is called the order of the geometry.
  • There are n+1 points in every line.
  • From every point, pass exactly n+1 lines.

  • Total number of lines is also Q .

  • And finally, if n is prime, then there does exists a geometry of order n .

    • What does that have to do with the puzzle, one may ask.

    Put card instead of point and picture instead of line and the axioms become:

  • Every two cards have exactly one picture in common.
  • For every two pictures there is exactly one card that has both of them.

    • Now, lets take n=7 and we have the order-7 finite geometry with Q = 7^2 + 7 + 1 . That makes Q=57 lines (pictures) and Q=57 points (cards). I guess the puzzle makers decided that 55 is more round number than 57 and left 2 cards out.

    We also get n+1 = 8 , so from every point (card), 8 lines pass (8 pictures appear) and every line (picture) has 8 points (appears in 8 cards).

    Here's a representation of the most famous finite projective (order-2) plane (geometry) with 7 points, known as Fano Plane , copied from Noelle Evans - Finite Geometry Problem Page

    I was thinking of creating an image that explain how the above order-2 plane could be made a similar puzzle with 7 cards and 7 pictures, but then a link from the math.exchange twin question has exactly such a diagram: Dobble-et-la-geometrie-finie

    法诺飞机

    So there are k=55 cards containing m=8 pictures each from a pool of n pictures total. We can restate the question 'How many pictures n do we need, so that we can construct a set of k cards with only one shared picture between any pair of cards?' equivalently by asking:

    Given an n-dimensional vector space and the set of all vectors, which contain exactly m elements equal to one and all other zero, how big has n to be, so that we can find a set of k vectors, whose pairwise dot products are all equal to 1?

    There are exactly (n choose m) possible vectors to build pairs from. So we at least need a big enough n so that (n choose m) >= k. This is just a lower bound, so for fulfilling the pairwise compatibility constraint we possibly need a much higher n.

    Just for experimenting a bit i wrote a small Haskell program to calculate valid card sets:

    Edit: I just realized after seeing Neil's and Gajet's solution, that the algorithm i use doesn't always find the best possible solution, so everything below isn't necessarily valid. I'll try to update my code soon. 

    module Main where

cardCandidates n m = cardCandidates' [] (n-m) m
cardCandidates' buildup  0  0 = [buildup]
cardCandidates' buildup zc oc
    | zc>0 && oc>0 = zerorec ++ onerec
    | zc>0         = zerorec
    | otherwise    = onerec
    where zerorec = cardCandidates' (0:buildup) (zc-1) oc
          onerec  = cardCandidates' (1:buildup) zc (oc-1)

dot x y = sum $ zipWith (*) x y
compatible x y = dot x y == 1

compatibleCards = compatibleCards' []
compatibleCards' valid     [] = valid
compatibleCards' valid (c:cs)
  | all (compatible c) valid = compatibleCards' (c:valid) cs
  |                otherwise = compatibleCards'    valid  cs

legalCardSet n m = compatibleCards $ cardCandidates n m

main = mapM_ print [(n, length $ legalCardSet n m) | n<-[m..]]
  where m = 8

    The resulting maximum number of compatible cards for m=8 pictures per card for different number of pictures to choose from n for the first few n looks like this:

    This brute force method doesn't get very far though because of combinatorial explosion. But i thought it might still be interesting.

    Interestingly, it seems that for given m, k increases with n only up to a certain n, after which it stays constant.

    This means, that for every number of pictures per card there is a certain number of pictures to choose from, that results in maximum possible number of legal cards. Adding more pictures to choose from past that optimal number doesn't increase the number of legal cards any further.

    The first few optimal k's are:

    链接地址: http://www.djcxy.com/p/80496.html

    上一篇: 2048比赛：我做了多少次动作？

    下一篇: 这个游戏背后的数学/计算原理是什么？