0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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) $\endgroup$ – Jean Marie Apr 3 '17 at 22:07
  • $\begingroup$ (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). $\endgroup$ – Jean Marie Apr 3 '17 at 22:08
  • $\begingroup$ I was forgetting, the number of symbols per card is $p+1$ (so 8 for the usual Dobble game) $\endgroup$ – Jean Marie Apr 3 '17 at 22:46
  • $\begingroup$ 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. $\endgroup$ – Simon Bohnen Apr 4 '17 at 7:45
  • 1
    $\begingroup$ 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" ? $\endgroup$ – Jean Marie Apr 4 '17 at 9:17
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.