# What is the minimal number of different symbols in the game “Dobble”?

There is a game called "Dobble" (or "Spot It!" in some countries) which implies an interesting problem I couldn't solve. The game consists of some amount of cards $c$, which have $s$ distinguishable symbols on them. For every two cards it is guaranteed that they have exactly one symbol in common. Several other questions have been asked about this game (see https://stackoverflow.com/questions/6240113/what-are-the-mathematical-computational-principles-behind-this-game), but I haven't found my question anywhere. I asked myself:

Given the total number of cards $c$ and the number of symbols $s$ per card, what is the minimum number of distinguishable symbols one has to use in order to fulfill the abovementioned condition?

I wrote an algorithm which can answer this question in a reasonable time for $c < 6$ and $s < 6$ in Java, it can be found here. I'm basically using brute-force to check all possibilities until I can be sure that I've found the optimal one. I used some if-clauses to bail out as early as possible and not generate useless possibiilities, but nevertheless the algorithm isn't fast enough for bigger numbers. If anyone is interested, I would explain the code in more detail (the comments I made are in German).

Here is a table with the values I got so far (extended table can be found here):

+---+---+---+----+----+----+----+
|   | 1 | 2 |  3 |  4 |  5 |  6 |  <- c
+---+---+---+----+----+----+----+
| 1 | 1 | 1 |  1 |  1 |  1 |  1 |
| 2 | 2 | 3 |  3 |  5 |  6 |  7 |
| 3 | 3 | 5 |  6 |  6 |  7 |  7 |
| 4 | 4 | 7 |  9 | 10 | 10 | 11 |
| 5 | 5 | 9 | 12 | 14 | 15 | 15 |
+---+---+---+----+----+----+----+
^
|
s

If $m(c, s)$ denotes the minimal number of distinguishable symbols, we can write down some (trivial) things:

• $m(1, s) = s$
• $m(2, s) = 2s - 1$
• $m(c, 1) = 1$
• $m(c, s) \le c * (s - 1) + 1$

The last inequality comes from the fact that one can always create the following configuration to meat the criterion:

1 1 1 1 ...
2 4 6 8 ...
3 5 7 9 ...

One column represents one card. This pattern can be applied to any $c$ and $s$ and the amount of different symbols is always $c * (s - 1) + 1$.

Furthermore the columns seem to develop according to $m(c, s + 1) = m(c, s) + c$ for larger $s$ and the rows form according to $m(c + 1, s) = m(c, s) + s - 1$ for larger $c$.

I've also searched the Online Encyclopedia of Integer Sequences for rows and columns of this sequence, but I couldn't find any promising results.

Nevertheless, I have no idea how to develop a formula for such a problem and would be thankful for your help.

• Are you aware that this game is based on finite dimensional projective geometry on vector space $\mathbb{Z_p}^2$ where $p$ is a prime number ? The cards are lines containing points (the symbols). Two lines intersect on a single point, etc. The number of lines is $p^2+p+1$. Dobble game is based on $p=7$ which gives 57 cards (theoreticaly, but may be one of them is not represented). The prime numbers immediately a) before are p=5 and p=3 thus there is a Dobble game with 31 cards (ctd) – Jean Marie Apr 3 '17 at 22:07
• (ctd...) or with 13 cards (not very interesting) b) on the contrary, if we jump to p=11, there exist a Dobble game with 133 cards... I am not aware of other possibilities in between (with another theory). – Jean Marie Apr 3 '17 at 22:08
• I was forgetting, the number of symbols per card is $p+1$ (so 8 for the usual Dobble game) – Jean Marie Apr 3 '17 at 22:46
• I've read a bit about this, but I don't really understand how this should help answering my question. If I'm misunderstanding something, it would be nice if you could explain it with more detail. – Simon Bohnen Apr 4 '17 at 7:45
• Maybe we are not on the same wavelength... I have some difficulty to understand for example your last column (with 6 cards) what are the meaning of the figures 1,7,7,11,15... For example, does the figure 7 means "number of symbols by card" ? – Jean Marie Apr 4 '17 at 9:17

The useful construction here is a $p\times p$ square lattice. Let's denote its nodes by the pair of $1..p$ indices, $(i,j)$. Our pool of symbols will consist of these pairs plus some other symbols.

We can use it for some estimates. For example, let's take $p$ sets of symbols of the form $\{(i,1),(i,2),\ldots,(i,p)\}$ (one such set for every $i$), and add to each of this set a new symbol, $r$. Now we have $p$ cards with $p+1$ symbols on each with the desired properties. Then take $p$ more sets of symbols of the form $\{(1,j),(2,j),\ldots,(p,j),r'\}$ with a new symbol, $r'$. So now we have $p^2+2$ symbols total and $2p$ cards with $p+1$ symbols on each, so $m(2p,p+1)\leqslant p^2+2$. If we add diagonal sets $\{(i+1\bmod p,1),(i+2\bmod p,2),\ldots,(i+p\bmod p,p),r''\}$, we obtain the estimate $m(3p,p+1)\leqslant p^2+3$. For odd $p$ only, we can also take antidiagonals and get $m(4p,p+1)\leqslant p^2+4$; and so on.

What JeanMarie says in the comment is that if $p$ is prime then we can draw straight lines through all $p+1$ inequivalent directions on our lattice including two orthogonal directions ($p$ lines in every set of lines corresponding to a particular direction), and each diagonal will cross every diagonal from any other set exactly once. Each set except $\{(1,j),(2,j),\ldots,(p,j),r'\}$ is given by $\{(i+k\bmod p,1),(i+2k\bmod p,2),\ldots,(i+pk\bmod p,p),r_k\}$ for a fixed $k\in[0;p)$. So we have $p+1$ sets (straight lines), each of which requires an additional symbol $r_k$ or $r'$ to form a card with $p+1$ symbols. Also, we can unite these additional symbols into one more card. So we have $p^2+(p+1)$ symbols and the same number, $p(p+1)+1$, of cards. For $p+1$ symbols per card, this is the optimal number of symbols: $m(p^2+p+1,p+1)=p^2+p+1$ for prime $p$. Thanks to JeanMarie again.

Also, one more trivial estimate: $\max(m(c-1,s),m(c,s-1))\leqslant m(c,s)\leqslant\min(m(c-1,s)+s,m(c,s-1)+c)$.

Proof of formula for c<=s+1:

If $$1\le c\le s$$ then each of the $$c$$ cards shares one symbol with each of the other $$c-1$$ cards. So each card has $$s-c+1$$ symbols that are not used on any other cards so far. Since $$c\le s$$, we have $$s-c+1 > 0$$. So we can create card $$c+1$$ by choosing one of these $$s-c+1$$ symbols from each of the $$c$$ previous cards, and we can be sure there will be no duplicates in these $$c$$ symbols. This gives us $$c$$ symbols on card $$c+1$$, and we need to add a further $$s-c$$ completely new symbols (note that $$s-c\ge0$$). So: $$m(c+1,s) = m(c,s) + s - c$$ And we know that $$m(1,s) = s$$, so $$m(2,s) = 2s - 1$$ ; $$m(3,s) = 3s -3$$ ... and in general $$m(c,s) = \sum_{k=0}^{c-1}(s-k) = cs - \frac{c(c-1)}{2}$$ for $$1\le c\le s+1$$. And, as special cases of this general formula: $$m(s,s) = m(s+1,s) = \frac{s(s+1)}{2}$$

I still don't have a formula for $$c>s+1$$.