Beim letzten Familienabend wurde das Spiel Dobble (in der Harry Potter Edition) begeistert von den Kindern zu Tisch gebracht. Nach der 5ten verlorenen Runde (ohne sichtbaren Treffer meiner Karte mit der Spielkarte) wurde mir unter meinem Erstaunen mitgeteilt, dass jeder Spieler in jeder Runde immer einen Treffer finden kann. Doch meine Ungläubigkeit wurde nur mit weiteren, verlorenen Runden quittiert – die Kinder waren einfach schneller.
Grund genug, sich das Spiel aus mathematischer Sicht genauer anzusehen. Zunächst zum Spielprinzip: Dobble ist ein simples Kartenspiel mit \(55\) runden Karten, die jeweils acht verschiedene Symbole zeigen. Alle Karten werden reihum ausgeteilt, nur die letzte Karte bleibt in der Tischmitte. Nun müssen alle Spieler gleichzeitig die Symbole auf der Karte mit den Symbolen ihrer aktuell oben liegenden Karte vergleichen. Hat ein Spieler das auf beiden Karten gleiche Symbol gefunden, kann er seine Karte auf den Stapel ablegen, indem er als Schnellster das Symbol benennt. Gewonnen hat der Spieler, der zuerst alle seine Karten abgelegt hat.
Wie kann es nun sein, dass es \(55\) solcher Karten gibt, die so konstruiert wurden, dass jeweils 2 beliebige Karten jeweils genau ein gemeinsames Symbol haben? Wie viele solcher Symbole müssen dazu minimal verwendet werden? Wie viele solcher Karten gibt es maximal?
Zunächst konstruieren wir diese Karten durch folgende logische Schritte (alle nachfolgend konstruierten Karten haben die Eigenschaft, dass sie aufsteigend sortiert sind): Die erste Karte muss 8 verschiedene Symbole tragen, lautet also:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Wie konstruieren nun die folgenden Karten so, dass sie mit der ersten Karte genau ein gemeinsames Symbol haben:
$$\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)$$
Bereits hier lassen sich beliebig viele solcher Karten konstruieren (man füllt die Stellen einfach aufsteigend beginnend mit \(9\) auf). Dieser triviale Fall ist aber uninteressant, da wir an einem Set mit minimaler Symbolanzahl (und maximaler Kartenzahl) interessiert sind. Wir betrachten nun jeweils das zweite Symbol \( x_{l.2} \) jeder Karte, für das offensichtlich gelten muss: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \). Wir haben also zwingend \( k \) neue Symbole eingeführt. Nun ist aber \( k \leq 8-1 = 7 \), da keines der \( 7 \) Symbole \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (der Karte ganz links) mit dem jeweils zweiten Symbol der anderen Karten übereinstimmen darf (sonst gäbe es zwei gleiche Symbole).
Damit haben wir maximal diese 7 neuen Karten gefunden:
$$\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)$$
Mit demselben Argument konstruieren wir nun die nächsten \(7\) Karten (die erste dieser Karten muss ja mit unserer Ausgangskarte kollidieren, und zwar nicht mit \(1\), da sie sonst bei den \(7\) zuvor gefundenen Karten wäre):
$$\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)$$
Dieses Argument lässt sich für die nächsten \(7\) Karten ebenso fortführen; Insgesamt noch \(8-2 = 6\) mal. Die letzten \(7\) Karten lauten demnach:
$$\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)$$
Würde man nun eine weitere Karte $$\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)$$ konstruieren wollen, misslingt dies, da diese Karte kein gemeinsames Symbol mit der Anfangskarte hat. Damit haben wir maximal \(1 + 8 \cdot 7 = 57\) Karten konstruiert. Unser Ziel ist es nun, auch minimal ebenso viele zu konstruieren.
Dazu sehen wie uns die ersten 7 neuen gefundenen Karten an und kommen zum Schluss, dass wir hier zwingend \(7 \cdot 7\) neue Symbole brauchen (keine Karte darf ein Symbol doppelt haben und jedes zu vergebene Symbol darf nicht doppelt vorkommen, da die \(1\) bereits doppelt ist):
$$\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)$$
Damit benötigen wir minimal \(8 + (7 \cdot 7) = 57\) Symbole (also genauso viele Symbole wie Karten!). Mit dieser Anzahl versuchen wir nun auszukommen und eine Konstruktionsvorschrift für alle anderen Elemente zu finden. Dazu konstruieren wir ein etwas kleineres Dobble, das nur \(3\) Symbole pro Karte trägt und erhalten als Anfangskarte
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
sowie die weiteren Karten
$$\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)$$
mit insgesamt \(1 + 3 \cdot 2 = 7\) Karten und \( 3 + (2 \cdot 2) = 7\) Symbolen. Durch etwas Probieren (und Einsetzen der bereits vergebenen Symbole) erhält man folgendes 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)$$
Lässt sich das auch systematisch finden? Dazu tragen wir die neu vergebenen Symbole \(4, 5, 6, 7\) in eine quadratische Matrix auf:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Nun denken wir uns für die ersten beiden Karten (beginnend bei den Startsymbolen \(4\) und \(5\)) vertikale Verbindungslinien zu den unteren Symbolen \(6\) und \(7\):
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Da sich diese Linien nicht schneiden, erhalten wir (durch zeilenweises Auftragen der Symbole an den Verbindungslinien) die nächsten gültigen Karten:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Schließlich denken wir uns Verbindungslinien mit einer anderen Steigung (in diesem Fall mit der Steigung \(1\)):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
Die zweite Verbindungslinie (zwischen \(5\) und \(6\)) verlässt die Matrix am rechten Rand und tritt am linken Rand wieder ein. Durch die geschickte Wahl der Steigung stellen wir zum einen sicher, dass sich die Verbindungslinien jeweils untereinander nicht schneiden aber auch die vorherigen (vertikalen) Verbindungslinien nicht schneiden. Diese Konstruktionsidee führt schlussendlich zu folgender Konstruktionsformel:
Ein Dobble mit \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) hat je \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) Karten und Symbole. Für die Karte \(K_x\) mit \(x \in \mathbb{N}\) und \(0 \leq x \leq (k-1) \cdot k\) gilt:
$$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.$$
Von diesen Karten gibt es damit \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) Stück. Nun ist nur noch abschließend zu zeigen:
$$ \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) $$
- 1. Fall: \( x_1 = 0 \)
- Fall 1a: \( 0 < x_2 < k \)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
\(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\). - Für \(y_1 \neq 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 = 1\) und \(y_2 \neq 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 \neq 1\) ist:
\(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\)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
- Fall 1b: \( x_2 \geq k \)
- Für \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_2 \neq 1\) ist:
\(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 \)
- Für \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) und \(y_2 = 1\) ist:
- Fall 1a: \( 0 < x_2 < k \)
- 2. Fall: \( 0 < x_1 < k \)
- Fall 2a: \( 0 < x_2 < k \)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 = 1\) und \(y_2 \neq 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 \neq 1\) ist:
\(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)\)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
- Fall 2b: \( x_2 \geq k \)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 = 1\) und \(y_2 \neq 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 \neq 1\) ist:
\((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) \)
Für \(y_2 = x_1+1\) mit \( 2 \leq y_2 \leq k\) ist
\(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)\) mit \( 2 \leq y_1 \leq k\).
Hier gibt es auch nur genau eine Lösung \( (y_1, y_2) \).
Wählen wir nämlich \(y^*_2=y_2-1\) als Wert, ist \(y^*_1 = y_1-(k-1) < 2\).
Außerdem ist für \(y^*_2*=y_2+1\) dann \(y^*_1 = y_1+(k-1) > k\).
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
- Fall 2a: \( 0 < x_2 < k \)
- 3. Fall: \( x_1 \geq k \)
- Fall 3a: \( x_2 \geq k \)
- Fall 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\)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
\(f(x_1, y_1) = f(x_1, 1) = m_1\)
\(f(x_2, y_2) = f(x_2, 1) = m_2 = m_1\) - Für \(y_1 = 1\) und \(y_2 \neq 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 = 1\) ist:
Siehe \(y_1 = 1\) und \(y_2 \neq 1\). - Für \(y_1 \neq 1\) und \(y_2 \neq 1\) ist:
\(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)\)
Dann ist \(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)\)
Für \(y_1 \neq y_2\) ist \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Für \(y_1 = y_2\) ist \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) und
\(\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\) im Widerspruch zu \(m_1 = m_2\).
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
- Fall 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\)
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
\(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\) - Für \(y_1 = 1\) und \(y_2 \neq 1\) ist:
\(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\) - Für \(y_1 \neq 1\) und \(y_2 = 1\) ist:
Siehe \(y_1 = 1\) und \(y_2 \neq 1\). - Für \(y_1 \neq 1\) und \(y_2 \neq 1\) ist:
\(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)\)
Dann ist \(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)\)
Für \(y_1 \neq y_2\) ist \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Für \(y_1 = y_2\) ist \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) und
\(\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}\)
Nun gibt es für \(2 \leq y \leq k\) immer ein \(l \in \mathbb{N}_0\), sodass
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Beweis: Da \((k-1)\) prim ist, ist (wg. dem Lemma von Bézout)
\((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
lösbar, denn \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) teilt \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
Dann ist dies aber auch die einzige Lösung \(l_1\), denn für ein
\(l_2 = l_1 + (m_2-m_1)\) ist \( y_2 = y_1 + (k-1) > k\).
- Für \(y_1 = 1\) und \(y_2 = 1\) ist:
- Fall 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\)
- Fall 3a: \( x_2 \geq k \)
Zum Thema Dobble und Mathematik findet man auch beispielsweise hier oder hier interessante Hintergrundinformationen. In folgendem Script sieht man die zuvor bewiesene Formel in Aktion: Damit lassen sich (für \((k-1)\) prim) Dobbles auf Knopfdruck generieren:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.