# Mathematics in the game Dobble0322

At the last family evening, the game Dobble (in the Harry Potter Edition) was enthusiastically brought to the table by the children. After the 5th lost round (with no visible hit of my card with the playing card) I was told, to my astonishment, that every player can always find a hit in every round. But my disbelief was only acknowledged with further lost laps - the children were simply faster.

Reason enough to take a closer look at the game from a mathematical point of view. First the game principle: Dobble is a simple card game with $$55$$ round cards, each showing eight different symbols. All cards are dealt in turn, leaving only the last card in the middle of the table. Now all players have to simultaneously compare the symbols on the card with the symbols on their current top card. If a player has found the same symbol on both cards, he can place his card on the stack by being the fastest to name the symbol. The player who discards all their cards first wins.

How can it be that there are $$55$$ such cards that were constructed in such a way that any 2 cards have exactly one symbol in common? What is the minimum number of such symbols that must be used? What is the maximum number of such cards?

First, we construct these cards using the following logical steps (all subsequently constructed cards have the property that they are sorted in ascending order): The first card must have 8 different symbols, i.e. reads:

$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$

We now construct the following cards in such a way that they have exactly one symbol in common with the first card:

$$\left(\begin{array}{c} 1 \\ x_{1.2} \\ x_{1.3} \\ x_{1.4} \\ x_{1.5} \\ x_{1.6} \\ x_{1.7} \\ x_{1.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{2.2} \\ x_{2.3} \\ x_{2.4} \\ x_{2.5} \\ x_{2.6} \\ x_{2.7} \\ x_{2.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{3.2} \\ x_{3.3} \\ x_{3.4} \\ x_{3.5} \\ x_{3.6} \\ x_{3.7} \\ x_{3.8} \end{array}\right), \ldots, \left(\begin{array}{c} 1 \\ x_{k.2} \\ x_{k.3} \\ x_{k.4} \\ x_{k.5} \\ x_{k.6} \\ x_{k.7} \\ x_{k.8} \end{array}\right)$$

Any number of such cards can already be constructed here (you simply fill in the places in ascending order, starting with $$9$$ ). This trivial case is uninteresting, however, since we are interested in a set with a minimum number of symbols (and a maximum number of cards). We now consider the second symbol $$x_{l.2}$$ of each card, for which obviously the following must apply: $$x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2}$$ . We have therefore necessarily introduced $$k$$ new symbols. But now $$k \leq 8-1 = 7$$ , since none of the $$7$$ symbols $$x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8}$$ (of the leftmost card) may match the second symbol of each of the other cards (otherwise there would be two identical symbols).

We have found a maximum of these 7 new cards:

$$\left(\begin{array}{c} 1 \\ x_{1.2} \\ x_{1.3} \\ x_{1.4} \\ x_{1.5} \\ x_{1.6} \\ x_{1.7} \\ x_{1.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{2.2} \\ x_{2.3} \\ x_{2.4} \\ x_{2.5} \\ x_{2.6} \\ x_{2.7} \\ x_{2.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{3.2} \\ x_{3.3} \\ x_{3.4} \\ x_{3.5} \\ x_{3.6} \\ x_{3.7} \\ x_{3.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{4.2} \\ x_{4.3} \\ x_{4.4} \\ x_{4.5} \\ x_{4.6} \\ x_{4.7} \\ x_{4.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{5.2} \\ x_{5.3} \\ x_{5.4} \\ x_{5.5} \\ x_{5.6} \\ x_{5.7} \\ x_{5.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{6.2} \\ x_{6.3} \\ x_{6.4} \\ x_{6.5} \\ x_{6.6} \\ x_{6.7} \\ x_{6.8} \end{array}\right), \left(\begin{array}{c} 1 \\ x_{7.2} \\ x_{7.3} \\ x_{7.4} \\ x_{7.5} \\ x_{7.6} \\ x_{7.7} \\ x_{7.8} \end{array}\right)$$

With the same argument we now construct the next $$7$$ maps (the first of these maps has to collide with our starting map, and not with $$1$$ , otherwise it would be with the $$7$$ previously found maps ):

$$\left(\begin{array}{c} 2 \\ x_{8.2} \\ x_{8.3} \\ x_{8.4} \\ x_{8.5} \\ x_{8.6} \\ x_{8.7} \\ x_{8.8} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{9.2} \\ x_{9.3} \\ x_{9.4} \\ x_{9.5} \\ x_{9.6} \\ x_{9.7} \\ x_{9.8} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{10.2} \\ x_{10.3} \\ x_{10.4} \\ x_{10.5} \\ x_{10.6} \\ x_{10.7} \\ x_{10.8} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{11.2} \\ x_{11.3} \\ x_{11.4} \\ x_{11.5} \\ x_{11.6} \\ x_{11.7} \\ x_{11.8} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{12.2} \\ x_{12.3} \\ x_{12.4} \\ x_{12.5} \\ x_{12.6} \\ x_{12.7} \\ x_{12.8} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{13.2} \\ x_{13.3} \\ x_{13.4} \\ x_{13.5} \\ x_{13.6} \\ x_{13.7} \\ x_{13.8} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{14.2} \\ x_{14.3} \\ x_{14.4} \\ x_{14.5} \\ x_{14.6} \\ x_{14.7} \\ x_{14.8} \end{array}\right)$$

This argument can also be continued for the next $$7$$ cards; A total $$8-2 = 6$$ more times. The last $$7$$ cards are accordingly:

$$\left(\begin{array}{c} 8 \\ x_{50.2} \\ x_{50.3} \\ x_{50.4} \\ x_{50.5} \\ x_{50.6} \\ x_{50.7} \\ x_{50.8} \end{array}\right), \left(\begin{array}{c} 8 \\ x_{51.2} \\ x_{51.3} \\ x_{51.4} \\ x_{51.5} \\ x_{51.6} \\ x_{51.7} \\ x_{51.8} \end{array}\right), \left(\begin{array}{c} 8 \\ x_{52.2} \\ x_{52.3} \\ x_{52.4} \\ x_{52.5} \\ x_{52.6} \\ x_{52.7} \\ x_{52.8} \end{array}\right), \left(\begin{array}{c} 8 \\ x_{53.2} \\ x_{53.3} \\ x_{53.4} \\ x_{53.5} \\ x_{53.6} \\ x_{53.7} \\ x_{53.8} \end{array}\right), \left(\begin{array}{c} 8 \\ x_{54.2} \\ x_{54.3} \\ x_{54.4} \\ x_{54.5} \\ x_{54.6} \\ x_{54.7} \\ x_{54.8} \end{array}\right), \left(\begin{array}{c} 8 \\ x_{55.2} \\ x_{55.3} \\ x_{55.4} \\ x_{55.5} \\ x_{55.6} \\ x_{55.7} \\ x_{55.8} \end{array}\right), \left(\begin{array}{c} 8 \\ x_{56.2} \\ x_{56.3} \\ x_{56.4} \\ x_{56.5} \\ x_{56.6} \\ x_{56.7} \\ x_{56.8} \end{array}\right)$$

If you were to add another card $$\left(\begin{array}{c} 9 \\ x_{57.2} \\ x_{57.3} \\ x_{57.4} \\ x_{57.5} \\ x_{57.6} \\ x_{57.7} \\ x_{57.8} \end{array}\right)$$ will fail because this card does not share a symbol with the starting card. We have constructed a maximum of $$1 + 8 \cdot 7 = 57$$ maps. Our goal now is to construct at least as many.

To do this, we look at the first 7 new cards found and come to the conclusion that we absolutely need $$7 \cdot 7$$ new symbols here (no card may have a symbol twice and each symbol to be assigned must not appear twice, since which $$1$$ is already double):

$$\left(\begin{array}{c} 1 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 15 \end{array}\right), \left(\begin{array}{c} 1 \\ 16 \\ 17 \\ 18 \\ 19 \\ 20 \\ 21 \\ 22 \end{array}\right), \left(\begin{array}{c} 1 \\ 23 \\ 24 \\ 25 \\ 26 \\ 27 \\ 28 \\ 29 \end{array}\right), \left(\begin{array}{c} 1 \\ 30 \\ 31 \\ 32 \\ 33 \\ 34 \\ 35 \\ 36 \end{array}\right), \left(\begin{array}{c} 1 \\ 37 \\ 38 \\ 39 \\ 40 \\ 41 \\ 42 \\ 43 \end{array}\right), \left(\begin{array}{c} 1 \\ 44 \\ 45 \\ 46 \\ 47 \\ 48 \\ 49 \\ 50 \end{array}\right), \left(\begin{array}{c} 1 \\ 51 \\ 52 \\ 53 \\ 54 \\ 55 \\ 56 \\ 57 \end{array}\right)$$

So we need minimal $$8 + (7 \cdot 7) = 57$$ symbols (so as many symbols as cards!). We are now trying to get by with this number and to find a construction rule for all other elements. To do this, we construct a slightly smaller dobble that only has $$3$$ symbols per card and receive it as the starting card

$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$

and the other cards

$$\left(\begin{array}{c} 1 \\ 4 \\ 5 \end{array}\right), \left(\begin{array}{c} 1 \\ 6 \\ 7 \end{array}\right)$$

$$\left(\begin{array}{c} 2 \\ x_{3.2} \\ x_{3.3} \end{array}\right), \left(\begin{array}{c} 2 \\ x_{4.2} \\ x_{4.3} \end{array}\right)$$

$$\left(\begin{array}{c} 3 \\ x_{5.2} \\ x_{5.3} \end{array}\right), \left(\begin{array}{c} 3 \\ x_{6.2} \\ x_{6.3} \end{array}\right)$$

with a total of $$1 + 3 \cdot 2 = 7$$ cards and $$3 + (2 \cdot 2) = 7$$ symbols. With a little trial and error (and using the symbols already assigned) you get the following dobble:

$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$

$$\left(\begin{array}{c} 1 \\ 4 \\ 5 \end{array}\right), \left(\begin{array}{c} 1 \\ 6 \\ 7 \end{array}\right)$$

$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$

$$\left(\begin{array}{c} 3 \\ 4 \\ 7 \end{array}\right), \left(\begin{array}{c} 3 \\ 5 \\ 6 \end{array}\right)$$

Can this also be found systematically? To do this, we enter the newly assigned symbols $$4, 5, 6, 7$$ in a square matrix:

$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$

Now we imagine for the first two cards (starting with the start symbols \ $$4$$ and $$5$$ ) vertical connecting lines to the lower symbols $$6$$ and $$7$$:

$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$

Since these lines do not intersect, we get (by plotting the symbols on the connecting lines line by line) the closest valid cards:

$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$

Finally, we imagine connecting lines with a different slope (in this case with the slope $$1$$ ):

$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$

The second connecting line (between $$5$$ and $$6$$ ) leaves the matrix at the right edge and reenters at the left edge. By skilfully choosing the slope, we ensure on the one hand that the connecting lines do not intersect with each other, but also that the previous (vertical) connecting lines do not intersect. This design idea ultimately leads to the following design formula:

A dobble with $$k \in \mathbb{N} \, | \, (k-1) \text{ prim}$$ has $$1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)$$ cards and symbols. For the map $$K_x$$ with $$x \in \mathbb{N}$$ and $$0 \leq x \leq (k-1) \cdot k$$ applies:

$$K_x = \left(\begin{array}{c} f(x,1) \\ f(x,2) \\ \vdots \\ f(x,k) \end{array}\right), \,\, m = \left\lfloor \frac{x-1}{k-1} \right\rfloor + 1,$$

$$f(x,y) = \left\{\begin{array}{ll} y & \text{falls } x = 0 \\ \lfloor \frac{x-1}{k-1} \rfloor + 1, &\text{sonst falls } y = 1 \\ (k+1) + (k-1)(x-1) + (y-2), & \text{sonst falls } 0 < x < k \\ \left( \left((m-1)(k-1)+x\right)-1+ \left( (m-2)(y-2) \right) \right) \% (k-1) &\text{sonst} \\ + (k+1) + (k-1)(y-2)&\end{array}\right.$$

There are $$(k-1)\cdot k + 1 = k + (k-1)(k-1)$$ pieces of these cards. Now it only remains to show:

$$\forall x_1 < x_2 \in \{ 1, \ldots, k+(k-1)(k-1) \} \, \exists \, ! \, y_1, y_2 \in \{ 1, \ldots, k \}: f(x_1, y_1) = f(x_2, y_2)$$

• case number one: $$x_1 = 0$$
• Case 1a: $$0 < x_2 < k$$
• For $$y_1 = 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(0, 1) = 1$$
$$f(x_2, y_2) = f(x_2, 1) = \lfloor \frac{x_2-1}{k-1} \rfloor + 1 = 1$$ .
• For $$y_1 \neq 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(0, y_1) = y_1 \neq 1$$
$$f(x_2, y_2) = f(x_2, y_2) = \lfloor \frac{x_2-1}{k-1} \rfloor + 1 = 1$$
• For $$y_1 = 1$$ and $$y_2 \neq 1$$ have:
$$f(x_1, y_1) = f(0, 1) = 1$$
$$f(x_2, y_2) = f(x_2, y_2) = (k+1) + (k-1)(x-1) + (y-2) =$$
$$(k+1)(x-1) + (k-1) + y \geq (k+1)(x-1)+y > 1$$
• For $$y_1 \neq 1$$ and $$y_2 \neq 1$$ is:
$$f(x_1, y_1) = f(0, y_1) = y_1 \leq k$$
$$f(x_2, y_2) = f(x_2, y_2) = (k+1) + (k-1)(x-1) + (y-2) > k$$
• Case 1b: $$x_2 \geq k$$
• For $$y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$$ and $$y_2 = 1$$ we have:
$$f(x_1, y_1) = f(0, \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$$
$$f(x_2, y_2) = f(x_2, 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$$
• For $$y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$$ and $$y_2 = 1$$ is:
$$f(x_1, y_1) = f(0, y_1) = y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$$
$$f(x_2, y_2) = f(x_2, 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$$
• For $$y_2 \neq 1$$ is:
$$f(x_1, y_1) = f(0, y_1) = y_1 \leq k$$
$$f(x_2, y_2) = \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1)$$
$$+ (k+1) + (k-1)(y_2-2) \geq (k+1)+(k-1)(y_2-2) > k$$
• 2nd case: $$0 < x_1 < k$$
• Case 2a: $$0 < x_2 < k$$
• For $$y_1 = 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor + 1 = 1$$
$$f(x_2, y_2) = f(x_2, 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1 = 1$$
• For $$y_1 \neq 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(x_1, y_1) = (k+1)+(k-1)(x_1-1)+(y_1-2) > 1$$
$$f(x_2, y_2) = f(x_2, 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1 = 1$$
• For $$y_1 = 1$$ and $$y_2 \neq 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor + 1 = 1$$
$$f(x_2, y_2) = f(x_2, y_2) = (k+1)+(k-1)(x_2-1)+(y_2-2) > 1$$
• For $$y_1 \neq 1$$ and $$y_2 \neq 1$$ is:
$$f(x_1, y_1) = (k+1)+(k-1)(x_1-1)+(y_1-2) \leq$$
$$(k+1)+(k-1)(x_1-1)+(k-2)$$
$$f(x_2, y_2) = (k+1)+(k-1)(x_2-1)+(y_2-2) \geq$$
$$(k+1)+(k-1)((x_1+1)-1)+(y_2-2) =$$
$$(k+1)+(k-1)(x_1-1) + (k-1) + (y_2-2) \geq$$
$$(k+1)+(k-1)(x_1-1) + (k-1) + (2-2) \geq$$
$$(k+1)+(k-1)(x_1-1) + (k-1) > (k+1)+(k-1)(x_1-1) + (k-2)$$
• Case 2b: $$x_2 \geq k$$
• For $$y_1 = 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor + 1 = 1$$
$$f(x_2, y_2) = f(x_2, 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1 \geq \left\lfloor \frac{k-1}{k-1} \right\rfloor + 1 = 2 > 1$$
• For $$y_1 = 1$$ and $$y_2 \neq 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor + 1 = 1$$
$$f(x_2, y_2) = \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1)$$
$$+ (k+1) + (k-1)(y_2-2) \geq (k+1) + (k-1)(y_2-2) > 1$$
• For $$y_1 \neq 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = \left( \left((m_1-1)(k-1)+x_1\right)-1+ \left( (m_1-2)(y_1-2) \right) \right) \% (k-1)$$
$$+ (k+1) + (k-1)(y_1-2) \geq (k+1) + (k-1)(y_1-2) > 1$$
$$f(x_2, y_2) = f(x_2, 1) = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1 = 1$$
• For $$y_1 \neq 1$$ and $$y_2 \neq 1$$ is:
$$(k+1) + (k-1)(x_1-1) + (y_1-2) =$$
$$\left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1)$$
$$+ (k+1) + (k-1)(y-2)$$
$$\Leftrightarrow y_1 = (k-1)y_2 - (k-1)(x_1+1) +$$
$$\left( 2 + \left( \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1) \right) \right)$$
For $$y_2 = x_1+1$$ with $$2 \leq y_2 \leq k$$ is
$$y_1 = 2 + \left( \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1) \right)$$ with $$2 \leq y_1 \leq k$$.
There is only one solution here $$(y_1, y_2)$$.
Because we choose $$y^*_2=y_2-1$$ as value, is $$y^*_1 = y_1-(k-1) < 2$$.
In addition, for $$y^*_2*=y_2+1$$ then $$y^*_1 = y_1+(k-1) > k$$.
• 3. Case: $$x_1 \geq k$$
• Case 3a: $$x_2 \geq k$$
• Case 3a': $$m_1 = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor +1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor +1 = m_2$$
• For $$y_1 = 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = m_1$$
$$f(x_2, y_2) = f(x_2, 1) = m_2 = m_1$$
• For $$y_1 = 1$$ and $$y_2 \neq 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = m_1 = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor + 1 \leq \left\lfloor \frac{((k-1) \cdot k)-1}{k-1} \right\rfloor + 1 =$$
$$\left\lfloor k - \frac{1}{k-1} \right\rfloor + 1 = (k - 1) + 1 = k$$
$$f(x_2, y_2) = \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \%$$
$$(k-1) + (k+1) + (k-1)(y_2-2) \geq$$
$$(k+1) + (k-1)(y_2-2) \geq (k+1) > k$$
• For $$y_1 \neq 1$$ and $$y_2 = 1$$ have:
See $$y_1 = 1$$ and $$y_2 \neq 1$$ .
• For $$y_1 \neq 1$$ and $$y_2 \neq 1$$ is:
$$f(x_1, y_1) = \left( \left((m_1-1)(k-1)+x_1\right)-1+ \left( (m_1-2)(y_1-2) \right) \right) \%$$
$$(k-1) + (k+1) + (k-1)(y_1-2) = L_1 + (k+1) + (k-1)(y_1-2)$$
$$f(x_2, y_2) = \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \%$$
$$(k-1) + (k+1) + (k-1)(y_2-2) = L_2 + (k+1) + (k-1)(y_2-2)$$
Then $$f(x_1, y_1) = f(x_2, y_2) \Leftrightarrow$$
$$L_1 + (k+1) + (k-1)(y_1-2) = L_2 + (k+1) + (k-1)(y_2-2) \Leftrightarrow$$
$$L_1 + (k-1)(y_1-2) = L_2 + (k-1)(y_2-2) \Leftrightarrow$$
$$L_1 - L_2 = (k-1)(y_2-y_1)$$
For $$y_1 \neq y_2$$ is $$L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)$$.
For $$y_1 = y_2$$ is $$L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2$$ and
$$\left( \left((m_1-1)(k-1)+x_1\right)-1+ \left( (m_1-2)(y_1-2) \right) \right) \% (k-1) =$$
$$\left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1) \Leftrightarrow$$
$$x_1 = x_2 + (k-1)\cdot l$$ in contradiction to $$m_1 = m_2$$.
• Case 3a'': $$m_1 = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor +1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor +1 = m_2$$
• For $$y_1 = 1$$ and $$y_2 = 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = m_1$$
$$f(x_2, y_2) = f(x_2, 1) = m_2 \neq m_1$$
• For $$y_1 = 1$$ and $$y_2 \neq 1$$ have:
$$f(x_1, y_1) = f(x_1, 1) = m_1 = \left\lfloor \frac{x_1-1}{k-1} \right\rfloor + 1 \leq \left\lfloor \frac{((k-1) \cdot k)-1}{k-1} \right\rfloor + 1 =$$
$$\left\lfloor k - \frac{1}{k-1} \right\rfloor + 1 = (k - 1) + 1 = k$$
$$f(x_2, y_2) = \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \%$$
$$(k-1) + (k+1) + (k-1)(y_2-2) \geq$$
$$(k+1) + (k-1)(y_2-2) \geq (k+1) > k$$
• For $$y_1 \neq 1$$ and $$y_2 = 1$$ have:
See $$y_1 = 1$$ and $$y_2 \neq 1$$ .
• For $$y_1 \neq 1$$ and $$y_2 \neq 1$$ is:
$$f(x_1, y_1) = \left( \left((m_1-1)(k-1)+x_1\right)-1+ \left( (m_1-2)(y_1-2) \right) \right) \%$$
$$(k-1) + (k+1) + (k-1)(y_1-2) = L_1 + (k+1) + (k-1)(y_1-2)$$
$$f(x_2, y_2) = \left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \%$$
$$(k-1) + (k+1) + (k-1)(y_2-2) = L_2 + (k+1) + (k-1)(y_2-2)$$
Then $$f(x_1, y_1) = f(x_2, y_2) \Leftrightarrow$$
$$L_1 + (k+1) + (k-1)(y_1-2) = L_2 + (k+1) + (k-1)(y_2-2) \Leftrightarrow$$
$$L_1 + (k-1)(y_1-2) = L_2 + (k-1)(y_2-2) \Leftrightarrow$$
$$L_1 - L_2 = (k-1)(y_2-y_1)$$
For $$y_1 \neq y_2$$ is $$L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)$$.
For $$y_1 = y_2$$ is $$L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2$$ and
$$\left( \left((m_1-1)(k-1)+x_1\right)-1+ \left( (m_1-2)(y_1-2) \right) \right) \% (k-1) =$$
$$\left( \left((m_2-1)(k-1)+x_2\right)-1+ \left( (m_2-2)(y_2-2) \right) \right) \% (k-1) \Leftrightarrow$$
$$y = \frac{(k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)}{m_2 - m_1}$$
Well there for $$2 \leq y \leq k$$ always a $$l \in \mathbb{N}_0$$, so that
$$m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)$$.
Proof: there $$(k-1)$$ is prime, is (because of Bézout's lemma)
$$(k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)$$
solvable, because $$\text{ggT}\left((k-1),(m_2-m_1)\right) = 1$$ Splits $$-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)$$.
Then this is the only solution $$l_1$$, because for one
$$l_2 = l_1 + (m_2-m_1)$$ is $$y_2 = y_1 + (k-1) > k$$.

You can also find interesting background information on the topic of dobble and mathematics here or here . In the following script you can see the previously proven formula in action: Dobbles (for $$(k-1)$$ prim) can be generated with the push of a button:

See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.

Back