What are the mathematical/computational principles behind this game?

Question

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

For those who have trouble picturing the projective plane geometry with 57 points, there is a really nice, intuitive way to construct the game with 57 cards and 57 symbols (based on the answer by Yuval Filmus for this question):

1. For cards with 8 symbols, create a 7x7 grid of unique symbols.
2. Add an additional 8 symbols for the "slopes" from 0 to 6, plus one for infinity slope.
3. Each card is a line on the grid (7 symbols) plus one symbol from the slope set for the slope of the line. Lines have an offset (i.e. starting point on the left), and a slope (i.e. how many symbols to go up for each step right). When the line leaves the grid at the top, re-enter at the bottom. See this example figure (pictures from boardgamegeek) for two such cards:

In the example, I take one line with slope zero (red), and one with slope 1 (green). They intersect at exactly one common point (the owl).

This method ensures that any two cards have exactly one common symbol, because

1. If the slopes are different, then the lines will always intersect at exactly one point.
2. If the slopes are the same, then the lines will not intersect and there will be no common symbol from the grid. In this case, the slope symbol will be the same.

In this way, we can construct 7x7 cards (7 offsets and 7 slopes).

We can also construct seven additional cards from vertical lines through the grid (i.e. taking each column). For those, the infinity slope icon is used.

Because each card consists of seven symbols from the grid and exactly one "slope" symbol, we can create one additional card, which simply consists of all the 8 slope symbols.

This leaves us with 7x8 + 1 = 57 possible cards, and 7 x 7 + 8 = 57 required symbols.

(Naturally, this only works with a prime-number-sized grid (e.g. n=7). Otherwise, lines of different slope could have zero or more than one intersection if the slope is a divisor of the grid size.)

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:

Others have described the general framework for the design (finite projective plane) and shown how to generate finite projective planes of prime order. I would just like to fill in some gaps.

Finite projective planes can be generated for many different orders, but they are most straightforward in the case of prime order p. Then the integers modulo p form a finite field which can be used to describe coordinates for the points and lines in the plane. There are 3 different kinds of coordinates for points: (1,x,y), (0,1,x), and (0,0,1), where x and y can take on values from 0 to p-1. The 3 different kinds of points explains the formula p^2+p+1 for the number of points in the system. We can also describe lines with the same 3 different kinds of coordinates: [1,x,y], [0,1,x], and [0,0,1].

We compute whether a point and line are incident by whether the dot product of their coordinates is equal to 0 mod p. So for example the point (1,2,5) and the line [0,1,1] are incident when p=7 since 1*0+2*1+5*1 = 7 == 0 mod 7, but the point (1,3,3) and the line [1,2,6] are not incident since 1*1+3*2+3*6 = 25 != 0 mod 7.

Translating into the language of cards and pictures, that means the card with coordinates (1,2,5) contains the picture with coordinates [0,1,1], but the card with coordinates (1,3,3) does not contain the picture with coordinates [1,2,6]. We can use this procedure to develop a complete list of cards and the pictures that they contain.

By the way, I think it's easier to think of pictures as points and cards as lines, but there's a duality in projective geometry between points and lines so it really doesn't matter. However, in what follows I will be using points for pictures and lines for cards.

The same construction works for any finite field. We know that there is a finite field of order q if and only if q=p^k, a prime power. The field is called GF(p^k) which stands for "Galois field". The fields are not as easy to construct in the prime power case as they are in the prime case.

Fortunately, the hard work has already been done and implemented in free software, namely Sage. To get a projective plane design of order 4, for example, just type

print designs.ProjectiveGeometryDesign(2,1,GF(4,'z'))

and you'll obtain output that looks like

ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20], blocks=[[0, 1, 2, 3, 20], [0,
4, 8, 12, 16], [0, 5, 10, 15, 19], [0, 6, 11, 13, 17], [0, 7, 9, 14,
18], [1, 4, 11, 14, 19], [1, 5, 9, 13, 16], [1, 6, 8, 15, 18], [1, 7,
10, 12, 17], [2, 4, 9, 15, 17], [2, 5, 11, 12, 18], [2, 6, 10, 14, 16],
[2, 7, 8, 13, 19], [3, 4, 10, 13, 18], [3, 5, 8, 14, 17], [3, 6, 9, 12,
19], [3, 7, 11, 15, 16], [4, 5, 6, 7, 20], [8, 9, 10, 11, 20], [12, 13,
14, 15, 20], [16, 17, 18, 19, 20]]>

I interpret the above as follows: there are 21 pictures labeled from 0 to 20. Each of the blocks (line in projective geometry) tells me which pictures appears on a card. For example, the first card will have pictures 0, 1, 2, 3, and 20; the second card will have pictures 0, 4, 8, 12, and 16; and so on.

The system of order 7 can be generated by

print designs.ProjectiveGeometryDesign(2,1,GF(7)) 

which generates the output

ProjectiveGeometryDesign<points=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46,
47, 48, 49, 50, 51, 52, 53, 54, 55, 56], blocks=[[0, 1, 2, 3, 4, 5, 6,
56], [0, 7, 14, 21, 28, 35, 42, 49], [0, 8, 16, 24, 32, 40, 48, 50], [0,
9, 18, 27, 29, 38, 47, 51], [0, 10, 20, 23, 33, 36, 46, 52], [0, 11, 15,
26, 30, 41, 45, 53], [0, 12, 17, 22, 34, 39, 44, 54], [0, 13, 19, 25,
31, 37, 43, 55], [1, 7, 20, 26, 32, 38, 44, 55], [1, 8, 15, 22, 29, 36,
43, 49], [1, 9, 17, 25, 33, 41, 42, 50], [1, 10, 19, 21, 30, 39, 48,
51], [1, 11, 14, 24, 34, 37, 47, 52], [1, 12, 16, 27, 31, 35, 46, 53],
[1, 13, 18, 23, 28, 40, 45, 54], [2, 7, 19, 24, 29, 41, 46, 54], [2, 8,
14, 27, 33, 39, 45, 55], [2, 9, 16, 23, 30, 37, 44, 49], [2, 10, 18, 26,
34, 35, 43, 50], [2, 11, 20, 22, 31, 40, 42, 51], [2, 12, 15, 25, 28,
38, 48, 52], [2, 13, 17, 21, 32, 36, 47, 53], [3, 7, 18, 22, 33, 37, 48,
53], [3, 8, 20, 25, 30, 35, 47, 54], [3, 9, 15, 21, 34, 40, 46, 55], [3,
10, 17, 24, 31, 38, 45, 49], [3, 11, 19, 27, 28, 36, 44, 50], [3, 12,
14, 23, 32, 41, 43, 51], [3, 13, 16, 26, 29, 39, 42, 52], [4, 7, 17, 27,
30, 40, 43, 52], [4, 8, 19, 23, 34, 38, 42, 53], [4, 9, 14, 26, 31, 36,
48, 54], [4, 10, 16, 22, 28, 41, 47, 55], [4, 11, 18, 25, 32, 39, 46,
49], [4, 12, 20, 21, 29, 37, 45, 50], [4, 13, 15, 24, 33, 35, 44, 51],
[5, 7, 16, 25, 34, 36, 45, 51], [5, 8, 18, 21, 31, 41, 44, 52], [5, 9,
20, 24, 28, 39, 43, 53], [5, 10, 15, 27, 32, 37, 42, 54], [5, 11, 17,
23, 29, 35, 48, 55], [5, 12, 19, 26, 33, 40, 47, 49], [5, 13, 14, 22,
30, 38, 46, 50], [6, 7, 15, 23, 31, 39, 47, 50], [6, 8, 17, 26, 28, 37,
46, 51], [6, 9, 19, 22, 32, 35, 45, 52], [6, 10, 14, 25, 29, 40, 44,
53], [6, 11, 16, 21, 33, 38, 43, 54], [6, 12, 18, 24, 30, 36, 42, 55],
[6, 13, 20, 27, 34, 41, 48, 49], [7, 8, 9, 10, 11, 12, 13, 56], [14, 15,
16, 17, 18, 19, 20, 56], [21, 22, 23, 24, 25, 26, 27, 56], [28, 29, 30,
31, 32, 33, 34, 56], [35, 36, 37, 38, 39, 40, 41, 56], [42, 43, 44, 45,
46, 47, 48, 56], [49, 50, 51, 52, 53, 54, 55, 56]]>