Op de laatste familieavond werd het spel Dobble (in de Harry Potter Editie) enthousiast door de kinderen op tafel gebracht. Na de 5e verloren ronde (zonder zichtbare hit van mijn kaart met de speelkaart) kreeg ik tot mijn verbazing te horen dat elke speler in elke ronde altijd een hit kan vinden. Maar mijn ongeloof werd pas erkend met nog meer verloren ronden - de kinderen waren gewoon sneller.
Reden genoeg om het spel wiskundig onder de loep te nemen. Eerst het spelprincipe: Dobble is een eenvoudig kaartspel met \(55\) ronde kaarten met elk acht verschillende symbolen. Alle kaarten worden om de beurt gedeeld, zodat alleen de laatste kaart in het midden van de tafel overblijft. Nu moeten alle spelers tegelijkertijd de symbolen op de kaart vergelijken met de symbolen op hun huidige bovenste kaart. Als een speler op beide kaarten hetzelfde symbool heeft gevonden, kan hij zijn kaart op de stapel leggen door als snelste het symbool te benoemen. De speler die als eerste al zijn kaarten aflegt, wint.
Hoe kan het dat er \(55\) zulke kaarten zijn die zo zijn geconstrueerd dat elke 2 kaarten precies één symbool gemeen hebben? Wat is het minimum aantal van dergelijke symbolen dat moet worden gebruikt? Wat is het maximale aantal van dergelijke kaarten?
Eerst construeren we deze kaarten door de volgende logische stappen te volgen (alle daarna geconstrueerde kaarten hebben de eigenschap dat ze in oplopende volgorde zijn gesorteerd): De eerste kaart moet 8 verschillende symbolen hebben, d.w.z. leest:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
We construeren nu de volgende kaarten zo dat ze precies één symbool gemeen hebben met de eerste kaart:
$$\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)$$
Een willekeurig aantal van dergelijke kaarten kan hier al worden geconstrueerd (je vult de plaatsen gewoon in oplopende volgorde in, beginnend met \(9\) ). Dit triviale geval is echter oninteressant, aangezien we geïnteresseerd zijn in een set met een minimum aantal symbolen (en een maximum aantal kaarten). We beschouwen nu het tweede symbool \( x_{l.2} \) van elke kaart, waarvoor uiteraard het volgende moet gelden: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . We hebben daarom noodzakelijkerwijs \( k \) nieuwe symbolen geïntroduceerd. Maar nu \( k \leq 8-1 = 7 \) , aangezien geen van de \( 7 \) symbolen \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (van de meest linkse kaart) mogen overeenkomen met het tweede symbool van elk van de andere kaarten (anders zouden er twee identieke symbolen zijn ).
We hebben maximaal van deze 7 nieuwe kaarten gevonden:
$$\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)$$
Met hetzelfde argument construeren we nu de volgende \(7\) kaarten (de eerste van deze kaarten moet botsen met onze startkaart, en niet met \(1\) , anders zou het met de \(7\) eerder zijn gevonden kaarten):
$$\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)$$
Dit argument kan ook worden voortgezet voor de volgende \(7\) kaarten; In totaal nog \(8-2 = 6\) keer. De laatste \(7\) kaarten zijn dienovereenkomstig:
$$\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)$$
Als u nog een kaart zou toevoegen $$\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)$$ zal mislukken omdat deze kaart geen symbool deelt met de startkaart. We hebben maximaal \(1 + 8 \cdot 7 = 57\) kaarten geconstrueerd. Ons doel is nu om er minstens evenveel te bouwen.
Hiervoor kijken we naar de eerste 7 gevonden nieuwe kaarten en komen tot de conclusie dat we hier absoluut \(7 \cdot 7\) nieuwe symbolen nodig hebben (geen enkele kaart mag twee keer een symbool hebben en elk toe te wijzen symbool mag niet voorkomen tweemaal, aangezien \(1\) al dubbel is):
$$\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)$$
We hebben dus minimale \(8 + (7 \cdot 7) = 57\) symbolen nodig (dus evenveel symbolen als kaarten!). Met dit aantal proberen we nu rond te komen en voor alle andere elementen een constructieregel te vinden. Om dit te doen, construeren we een iets kleinere dobble die alleen \(3\) symbolen per kaart heeft en ontvangen deze als startkaart
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
en de andere kaarten
$$\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)$$
met in totaal \(1 + 3 \cdot 2 = 7\) kaarten en \( 3 + (2 \cdot 2) = 7\) symbolen. Met een beetje vallen en opstaan (en met behulp van de symbolen die al zijn toegewezen) krijg je de volgende 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)$$
Is dit ook systematisch terug te vinden? Hiervoor voeren we de nieuw toegekende symbolen \(4, 5, 6, 7\) in een vierkante matrix:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Nu stellen we ons voor de eerste twee kaarten (beginnend met de startsymbolen \ \(4\) en \(5\) ) verticale verbindingslijnen naar de onderste symbolen \(6\) en \(7\):
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Aangezien deze lijnen elkaar niet kruisen, krijgen we (door de symbolen op de verbindingslijnen lijn voor lijn uit te zetten) de dichtstbijzijnde geldige kaarten:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Ten slotte stellen we ons verbindingslijnen voor met een andere helling (in dit geval met de helling \(1\) ):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
De tweede verbindingslijn (tussen \(5\) en \(6\) ) verlaat de matrix aan de rechterrand en komt weer binnen aan de linkerrand. Door vakkundig het talud te kiezen zorgen we er enerzijds voor dat de verbindingslijnen elkaar niet kruisen, maar ook dat de voorgaande (verticale) verbindingslijnen elkaar niet kruisen. Dit ontwerpidee leidt uiteindelijk tot de volgende ontwerpformule::
Een dobble met \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) heeft \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) kaarten en symbolen. Voor de kaart \(K_x\) met \(x \in \mathbb{N}\) en \(0 \leq x \leq (k-1) \cdot k\) geldt:
$$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.$$
Er zijn \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) stukken van deze kaarten. Nu alleen nog om te laten zien:
$$ \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) $$
- 1e geval: \( x_1 = 0 \)
- Geval 1a: \( 0 < x_2 < k \)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
\(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\) . - Voor \(y_1 \neq 1\) en \(y_2 = 1\) we:
\(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\) - Voor \(y_1 = 1\) en \(y_2 \neq 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(y_2 \neq 1\) geldt:
\(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\)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
- Geval 1b: \( x_2 \geq k \)
- Voor \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) en \(y_2 = 1\) hebben we:
\(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\) - Voor \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) en \(y_2 = 1\) geldt:
\(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\) - Voor \(y_2 \neq 1\) geldt:
\(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 \)
- Voor \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) en \(y_2 = 1\) hebben we:
- Geval 1a: \( 0 < x_2 < k \)
- 2e geval: \( 0 < x_1 < k \)
- Geval 2a: \( 0 < x_2 < k \)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(y_2 = 1\) we:
\(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\) - Voor \(y_1 = 1\) en \(y_2 \neq 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(y_2 \neq 1\) geldt:
\(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)\)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
- Geval 2b: \( x_2 \geq k \)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
\(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\) - Voor \(y_1 = 1\) en \(y_2 \neq 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(y_2 = 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(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) \)
Voor \(y_2 = x_1+1\) met \( 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)\) met \( 2 \leq y_1 \leq k\).
Er is hier maar één oplossing \( (y_1, y_2) \).
Omdat we kiezen \(y^*_2=y_2-1\) als waarde, is \(y^*_1 = y_1-(k-1) < 2\).
Bovendien, voor \(y^*_2*=y_2+1\) dan \(y^*_1 = y_1+(k-1) > k\).
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
- Geval 2a: \( 0 < x_2 < k \)
- 3. Geval: \( x_1 \geq k \)
- Geval 3a: \( x_2 \geq k \)
- Geval 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\)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
\(f(x_1, y_1) = f(x_1, 1) = m_1\)
\(f(x_2, y_2) = f(x_2, 1) = m_2 = m_1\) - Voor \(y_1 = 1\) en \(y_2 \neq 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(y_2 = 1\) we:
Zie \(y_1 = 1\) en \(y_2 \neq 1\) . - Voor \(y_1 \neq 1\) en \(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)\)
Dan \(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)\)
Voor \(y_1 \neq y_2\) is \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Voor \(y_1 = y_2\) is \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) en
\(\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 tegenstelling tot \(m_1 = m_2\).
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
- Geval 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\)
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
\(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\) - Voor \(y_1 = 1\) en \(y_2 \neq 1\) we:
\(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\) - Voor \(y_1 \neq 1\) en \(y_2 = 1\) we:
Zie \(y_1 = 1\) en \(y_2 \neq 1\) . - Voor \(y_1 \neq 1\) en \(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)\)
Dan \(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)\)
Voor \(y_1 \neq y_2\) is \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Voor \(y_1 = y_2\) is \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) en
\(\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}\)
Nou daar voor \(2 \leq y \leq k\) altijd een \(l \in \mathbb{N}_0\), zodat
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Bewijs: daar \((k-1)\) is priemgetal, is (vanwege het lemma van Bézout)
\((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
oplosbaar, omdat \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Splitst \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
Dan is dit de enige oplossing \(l_1\), omdat voor een
\(l_2 = l_1 + (m_2-m_1)\) is \( y_2 = y_1 + (k-1) > k\).
- Voor \(y_1 = 1\) en \(y_2 = 1\) we:
- Geval 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\)
- Geval 3a: \( x_2 \geq k \)
Ook vindt u hier of hier interessante achtergrondinformatie over het onderwerp dobble en wiskunde. In het volgende script zie je de eerder bewezen formule in actie: Dobbles (voor \((k-1)\) prim) kunnen met een druk op de knop worden gegenereerd:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.