What are the mathematical/computational principles behind this game?

Question

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 (i.e. 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 (i.e. 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:

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

2. 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:

Solution 1

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

Solution 2

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.)

Solution 3

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:

Solution 4

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 picture with coordinates (1,2,5) is contained in the card with coordinates [0,1,1], but the picture with coordinates (1,3,3) is not contained in the card 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 Math. 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]]>

If you want up to 57 cards you can use GF(7). If you want 58 cards you'll have to use a larger field. Since 8 is a power of a prime, you could use GF(8,'z') (the z is a kind of "hidden variable" in the field; it doesn't matter what letter you use, as long as you haven't used that letter already in that Sage session). Note that the projective plane based on GF(8,'z') will have 8^2 + 8 + 1 = 73 points and 73 lines. You can make 73 cards, but then just throw away 15 of them if you want a set of exactly 58 cards. If you want between 73 and 91 cards you could use GF(9,'z'), etc. There is no GF(10) because 10 is not a power of a prime. GF(11) is next, then GF(13), then GF(16,'z') because 16=2^4, and so on.

By the way, I have a theory that the original Spot It deck uses 55, not 57, because they contracted a playing card manufacturer which was already tooled for decks of 55 cards (52 regular cards in a deck, plus two jokers and a title card).

Solution 5

I just found a way to do it with 57 or 58 pictures but now I have a very bad headache, I'll post the ruby code in 8-10 hours after I slept well! just a hint my my solution every 7 cards share same mark and total 56 cards can be constructed using my solution.

here is the code that generates all 57 cards that ypercube was talking about. it uses exactly 57 pictures, and sorry guy's I've written actual C++ code but knowing that vector <something> is an array containing values of type something it's easy to understand what this code does. and this code generates P^2+P+1 cards using P^2+P+1 pictures each containing P+1 picture and sharing only 1 picture in common, for every prime P value. which means we can have 7 cards using 7 pictures each having 3 pictures(for p=2), 13 cards using 13 pictures(for p=3), 31 cards using 31 pictures(for p=5), 57 cards for 57 pictures(for p=7) and so on...

#include <iostream>
#include <vector>

using namespace std;

vector <vector<int> > cards;

void createcards(int p)
{
    cards.resize(0);
    for (int i=0;i<p;i++)
    {
        cards.resize(cards.size()+1);
        for(int j=0;j<p;j++)
        {
            cards.back().push_back(i*p+j);
        }
        cards.back().push_back(p*p+1);
    }

    for (int i=0;i<p;i++)
    {
        for(int j=0;j<p;j++)
        {
            cards.resize(cards.size()+1);
            for(int k=0;k<p;k++)
            {
                cards.back().push_back(k*p+(j+i*k)%p);
            }
            cards.back().push_back(p*p+2+i);
        }
    }

    cards.resize(cards.size()+1);

    for (int i=0;i<p+1;i++)
        cards.back().push_back(p*p+1+i);
}

void checkCards()
{
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=0;j<cards[i].size();j++)
        {
            printf("%3d",cards[i][j]);
        }
        cout << "\n";
    }
    cout << "---------------------\n";
    for(unsigned i=0;i<cards.size();i++)
    {
        for(unsigned j=i+1;j<cards.size();j++)
        {
            int sim = 0;
            for(unsigned k=0;k<cards[i].size();k++)
                for(unsigned l=0;l<cards[j].size();l++)
                    if (cards[i][k] == cards[j][l])
                        sim ++;
            if (sim != 1)
                cout << "there is a problem between cards : " << i << " " << j << "\n";

        }
    }
}

int main()
{
    int p;
    for(cin >> p; p!=0;cin>> p)
    {
        createcards(p);
        checkCards();
    }
}

again sorry for the delayed code.

View more solutions

Comments

[Joris Ooms]

+1 for turning a game into something that hurts my brain.

[trutheality]

Minimum number of pictures per card, or minimum number of pictures given that there are 8 per card? Also, does every picture have to be matchable?

[mbeckish]

I think you need to add more constraints. Otherwise, you could put an apple on every card, and then add any number of unique images to each card. Each pair of cards will only match on the image of the apple.

[Admin]

@mbeckish I guess every picture only occurs twice per deck.

[Peter Alexander]

@mbeckish: If you did that then you wouldn't get the minimum number of pictures required.

[ypercubeᵀᴹ]

Excellent puzzle! Probably connected with (Finite) Projective Geometries.

[mbeckish]

@WTP - If that were the case, then You could have at most K cards in the deck, where K is the number of pictures on each card. If you want to have more cards in your deck, you would need to allow the same image to be involved in matching multiple pairs of cards.

[Callmeed]

Ok, I've updated the original question to try and clarify the comments here. @WTP pictures occurs much more often than twice per deck.

[Ali1S232]

@WTP and int the picture he posted there are 3 cards sharing same picture (spot them!)

[ypercubeᵀᴹ]

@Callmeed: If there were 57 (and not 55) cards in your set, I would bet that all pictures appear in exactly 8 cards. Now, I can bet that almost all pictures appear in 8 cards, except 14 pictures that appear in 7 cards and 1 picture that appears in 6 cards.

[ypercubeᵀᴹ]

Oh, and there is a total of exactly 57 different pictures in the set.

[dmckee --- ex-moderator kitten]

@cabaret: In that case you'll like set. Unbelievably fun and aggravating.

[Joe]

Great looking game. Going to have to pick that up for my kids.

[casperOne]

This should probably be on Mathematics

[Callmeed]

Am I allowed to cross-post this on Math SE?

[abcd]

@Calmeed: I guess you can probably cross-post it, but keep the objectives separate. If you post there, ask for the deeper mathematical details behind the game (no programming) and leave the Ruby/programming details for SO.

[Callmeed]

Ok, there's already a post about this game on Math. See math.stackexchange.com/questions/36798/…. According to a link on that post, there are 50 different pictures. No accepted answer though.

[Thies Heidecke]

@Callmeed: i posted a link to your question there, perhaps someone is also interested in this discussion here.

[Javid Jamae]

While this is a great question, its already been asked on the math site (by me). It seems a little off topic here. - math.stackexchange.com/questions/36798/…

[C. A. McCann]

This is a very interesting question with very interesting answers but it's also very off-topic for SO. :(

[b_jonas]

About the mathematical principles, see also David Madore's recent writeup "Le jeu de cartes Dobble et la géométrie projective expliquée aux enfants" madore.org/~david/weblog/… (note that "Dobble" is another for this game). See also math.stackexchange.com/q/464932/24908 , math.stackexchange.com/q/172771/24908 , math.stackexchange.com/q/36798/24908

[Kushal Jain]

Out of the topic : I found similar game on android play store play.google.com/store/apps/details?id=com.game.findone

[SamGoody]

For working JS code, see stackoverflow.com/q/52822827/87520

[sarnold]

I have an elegant proof of this, but alas this comment box is too small to contain it.

[Nemo]

That's just an initial attempt at a bound, right? You have not incorporated the "pairwise dot products equal to 1" requirement...

[BoltClock]

Apparently the syntax highlighter here doesn't really support Haskell yet (meta.stackexchange.com/questions/78363/…), but I'll toss in the hint just in case it does in future.

[Thies Heidecke]

@BoltClock thanks for your edit! i didn't know you could give hints for language-specific syntax highlighting.

[BoltClock]

It's not very well-known yet :)

[Thies Heidecke]

glad that you found the idea helpful. I like the illustration of the card set.

[RMorrisey]

So this game exhibits non-Euclidean geometry? Would it be correct to say that The Cards Are Right?

[Nate Kohl]

This sounds awesome, but I have no certainty that it actually models the problem well. @ypercube, could you explain a bit more why you think the analogy between card/picture and point/line is valid?

[Thies Heidecke]

i think the last three cards in your example aren't valid, because they don't share a picture with the fifth card. Just checked my code for over an hour before i realized it :) Interestingly, it seems the maximum size of a legal cardset is 5 for 4 pictures per card and doesn't increase even with more pictures to choose from.

[Neil G]

@Thies: Nice catch. Looks like this greedy algorithm doesn't work. My next approach is to do it recursively.

[Thies Heidecke]

@Neil: Looking forward to see what you come up with. I'll also try to do a new version of my code since the current one is kind of wasteful and therefore only feasible for small sizes at the moment.

[ypercubeᵀᴹ]

@Nate: The 1st analogy every two cards have exactly one picture in common, is stated in the question. The 2nd for every two pictures there is exactly one card that has both of them, the OP can tell us if the game set satisfies it.

[ypercubeᵀᴹ]

@Neil: Nice. Theory says that with PICTURES_PER_CARD = 4, you could have an arrangement of 3^2+3+1 = 13 cards and 13 pictures.

[ypercubeᵀᴹ]

@Gajet: Did you run it for p=4? (and 21 cards/pictures)

[Thies Heidecke]

@ypercube: that's interesting. Does the theory predict that there definitely should be 13 cards and pictures? because from my experiments it seems like this is just an upper bound that isn't reached in every case (e.g. for 4 pictures per card i got a maximum of 5 different cards with 10 pictures).

[Ali1S232]

4 isn't doesn't work in my algorithm since 4 is not a prime number, in my algorithm it's important that p should be prime.

[Ali1S232]

@ypercube after checking again there was some minior mistakes in my algorithm but i checked it for, 2 ,3,5,7 and I can prove for any other prime number it will work, so here is my complete code (but in c++)

[João Paladini]

Awesome answer! Great insight, realizing that the game matches the properties of an Order-7 Projective Plane, plus one of the best explanations of Projective Planes for laypersons that I have seen.

[ypercubeᵀᴹ]

@Thies: No, there are other arrangements, if you keep only the first axiom/condition: Given any 2 cards chosen from the deck, there is 1 and only 1 matching picture and not the second Given two pictures there is exactly 1 card that has both of them. The problem has connections with combinatorial block design, coding theory (like error-correction codes) and probably other areas of mathematics/computer science.

[ypercubeᵀᴹ]

@Gajet: Nice work. Just curious if it also solves the prime powers cases: 4, 8, 9, 16, ....

[Neil G]

@Gajet: I also ported your solution to Python to check it/understand it. I hope you don't mind. Feel free to move the ported code from my answer to yours if you want to.

[Neil G]

@Gajet: I also found a bug in your code: You never create card p*p. You can shift down some indices by 1.

[Neil G]

@Thies with the diagram I produced using Gajet's code, it's much easier to see why there are exactly (p) + (p * p) + (1) configurations.

[Ali1S232]

@Neil G: you are right, now you mention it i just wrote half of the code numbering from 0 to p^2+p and the other half numbering from 1 to p^2+p+1, that's why I skiped p*p. but i don't call that a bug specificly! and you upvoted after I mentioned it when i said you didn't it still had 2 votes! :D

[Neil G]

@Gajet: I also fixed your algorithm so that it works with non-prime numbers. Please let me know if it looks right to you.

[Ali1S232]

@neil : do you mean in your code or in mine? since mine doesn't seem to be changed at all.

[Ali1S232]

@NeilG: I think in your algorithm all the cards generated are valid but for non prime values of p, there are less than p*p+p+1 cards generated.

[Neil G]

@Gajet: Exactly. Is it really possible to have all p*p + p + 1 cards in those cases?

[Ali1S232]

@NeilG: As i explained to ypercube in my comments I think it's possible to generate for all p except 4 and 6. i'm refering to an axiom in ring theory, and the key is to change multiplication operator in k * p + (j + i * k) % p between i and k;

[Thies Heidecke]

@Gajet: cool solution! Now i get why my greedy algorithm didn't always produce the best solution.

[Thies Heidecke]

@Neil: Thanks for the updated diagram, makes it much easier to see how Gajet's solution works!

[ypercubeᵀᴹ]

@Gajet: I think you are wrong about all p except 4 and 6. If you want to produce a finite plane where there are p*p+p+1 points and lines (cards and pictures), then it's related to finite fields and not rings. There are finite fields of order p when p is prime or a prime power. Your code works correctly for primes because expressions like k * p + (j + i * k) % p are expressing k*p + j + i*k in terms of the multiplication and addition in the finite field of order p.

[ypercubeᵀᴹ]

It will work correctly for prime powers too, if you can express these operations (mult. and addition) in the finite fields of order p^2, p^3, etc. So, it will work for 4, 8, 9, 16, 25, 27, ...

[Neil G]

@ypercube: What is the solution for 4? Because this solution doesn't work for 4.

[Ali1S232]

@tpercube: yes i was rwong about 4 and 6, after more research it seems it can work at elast for any p^k, now i'm developing an algorithm that can handle addition and multiplication of p^k elements. right now i'm stuck with mutiplication, you can check math forum to see how I'm trying to construct these two operators.

[bonCodigo]

@ypercube +1 Brilliant :D This is just more than an answer to a question.

[Jared]

Brilliant. I'm going to need to read this 100 more times to try to figure out how to generate card sets in Python...

[DPF]

Does this mean that the is no solution for n being no prime or only that this method does not work then?

[DPF]

Does this mean, that you can't solve the problem for non prime n? Or is it just not represented by the projective plane approach?

[ypercubeᵀᴹ]

@DPF actually, solution exists for prime and prime powers (4,8,19,16,25,27,32,...). For the other composite numbers, it's mostly an open problem. I think I should update the answer with more details.

[Sven Zwei]

@DPF This particular method would not work. Other methods may still exist. A simple method that has been posted here (and that "works" with any number of symbols) would be to just brute force random cards until you have a deck.

[SamGoody]

What a clear answer - thank you for making the graphics! I have implemented it in JS at stackoverflow.com/a/67409457/87520