Matematyka w grze Dobble

W ostatni wieczór rodzinny gra Dobble (w Harry Potter Edition) została entuzjastycznie przyniesiona na stół przez dzieci. Po 5 przegranej rundzie (bez widocznego trafienia mojej karty z kartą do gry) powiedziano mi, ku mojemu zdumieniu, że każdy gracz zawsze może znaleźć trafienie w każdej rundzie. Ale moje niedowierzanie zostało potwierdzone dopiero kolejnymi straconymi okrążeniami - dzieci były po prostu szybsze.


To wystarczający powód, aby przyjrzeć się grze z matematycznego punktu widzenia. Najpierw zasada gry: Dobble to prosta gra karciana z \(55\) okrągłymi kartami, każda z ośmioma różnymi symbolami. Wszystkie karty są rozdawane po kolei, pozostawiając tylko ostatnią kartę na środku stołu. Teraz wszyscy gracze muszą jednocześnie porównać symbole na karcie z symbolami na swojej obecnej górnej karcie. Jeśli gracz znalazł ten sam symbol na obu kartach, może umieścić swoją kartę na stosie, najszybciej nazywając symbol. Gracz, który jako pierwszy odrzuci wszystkie swoje karty, wygrywa.

Jak to możliwe, że są \(55\) takie karty, które zostały skonstruowane w taki sposób, że dowolne 2 karty mają dokładnie jeden wspólny symbol? Jaka jest minimalna liczba takich symboli, których należy użyć? Jaka jest maksymalna liczba takich kart?

Najpierw konstruujemy te karty, stosując następujące logiczne kroki (wszystkie kolejno konstruowane karty mają tę właściwość, że są sortowane w kolejności rosnącej): Pierwsza karta musi mieć 8 różnych symboli, tj. odczytów:

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

Konstruujemy teraz następujące karty w taki sposób, aby miały dokładnie jeden symbol wspólny z pierwszą kartą:

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

Można tu już skonstruować dowolną liczbę takich kart (wystarczy wypełnić miejsca w kolejności rosnącej, zaczynając od \(9\) ). Ten banalny przypadek jest jednak nieciekawy, ponieważ interesuje nas zestaw z minimalną liczbą symboli (i maksymalną liczbą kart). Rozważmy teraz drugi symbol \( x_{l.2} \) każdej karty, do którego oczywiście muszą obowiązywać: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . Dlatego koniecznie wprowadziliśmy \( k \) nowe symbole. Ale teraz \( k \leq 8-1 = 7 \) , ponieważ żaden z \( 7 \) symboli \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (od lewej karty) może pasować do drugiego symbolu każdej z pozostałych kart (w przeciwnym razie byłyby dwa identyczne symbole ).

Znaleźliśmy maksymalnie 7 nowych kart:

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

Z tym samym argumentem konstruujemy teraz następne mapy \(7\) (pierwsza z tych map musi kolidować z naszą mapą startową, a nie z \(1\) , w przeciwnym razie byłaby z poprzednią \(7\) znalezione mapy ):

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

Argument ten można również kontynuować dla następnych kart \(7\) ; W sumie \(8-2 = 6\) więcej razy. Ostatnie \(7\) karty są odpowiednio:

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

Gdybyś miał dodać kolejną kartę $$\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)$$ nie powiedzie się, ponieważ ta karta nie ma wspólnego symbolu z kartą startową. Skonstruowaliśmy maksymalnie \(1 + 8 \cdot 7 = 57\) map. Naszym celem jest teraz zbudowanie co najmniej tylu.

Aby to zrobić, patrzymy na pierwsze 7 znalezionych nowych kart i dochodzimy do wniosku, że absolutnie potrzebujemy \(7 \cdot 7\) nowych symboli (żadna karta nie może mieć symbolu dwa razy i każdy symbol do przypisania nie może się pojawić dwa razy, od którego \(1\) jest już podwójne):

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

Potrzebujemy więc minimalnych symboli \(8 + (7 \cdot 7) = 57\) (a więc tyle symboli, ile kart!). Teraz próbujemy poradzić sobie z tą liczbą i znaleźć zasadę konstrukcji dla wszystkich innych elementów. Aby to zrobić, konstruujemy nieco mniejszy dobble, który ma tylko symbole \(3\) na kartę i otrzymujemy go jako kartę początkową

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

i inne karty

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

łącznie z kartami \(1 + 3 \cdot 2 = 7\) i symbolami \( 3 + (2 \cdot 2) = 7\) . Po odrobinie prób i błędów (i użyciu już przypisanych symboli) otrzymujesz następujące dublet:

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

Czy można to również znaleźć systematycznie? W tym celu wpisujemy nowo przypisane symbole \(4, 5, 6, 7\) do macierzy kwadratowej:

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

Teraz wyobraźmy sobie dla pierwszych dwóch kart (zaczynając od symboli początkowych \ \(4\) i \(5\) ) pionowe linie łączące z dolnymi symbolami \(6\) i \(7\):

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

Ponieważ te linie się nie przecinają, otrzymujemy (wykreślając symbole na liniach łączących linia po linii) najbliższe ważne karty:

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

Na koniec wyobrażamy sobie łączenie linii o różnym nachyleniu (w tym przypadku z nachyleniem \(1\) ):

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

Druga linia łącząca (pomiędzy \(5\) i \(6\) ) opuszcza macierz przy prawej krawędzi i ponownie wprowadza się przy lewej krawędzi. Umiejętnie dobierając spadek, zapewniamy z jednej strony, że łączniki nie przecinają się ze sobą, ale również, że poprzednie (pionowe) łączniki się nie przecinają. Ten pomysł projektowy ostatecznie prowadzi do następującej formuły projektowej:

Podbicie z \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) ma \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) karty i symbole. Dla mapy \(K_x\) z \(x \in \mathbb{N}\) i \(0 \leq x \leq (k-1) \cdot k\):

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

\((k-1)\cdot k + 1 = k + (k-1)(k-1)\) części tych kart. Teraz pozostaje tylko pokazać:

$$ \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 przypadek: \( x_1 = 0 \)
    • Przypadek 1a: \( 0 < x_2 < k \)
      • Dla \(y_1 = 1\) i \(y_2 = 1\) :
        \(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\) .
      • Dla \(y_1 \neq 1\) i \(y_2 = 1\) :
        \(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\)
      • Dla \(y_1 = 1\) i \(y_2 \neq 1\) :
        \(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\)
      • Dla \(y_1 \neq 1\) i \(y_2 \neq 1\) to:
        \(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\)
    • Przypadek 1b: \( x_2 \geq k \)
      • Dla \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) i \(y_2 = 1\) mamy:
        \(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\)
      • Dla \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) i \(y_2 = 1\) wynosi:
        \(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\)
      • Dla \(y_2 \neq 1\) to:
        \(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 \)
  • 2. przypadek: \( 0 < x_1 < k \)
    • Przypadek 2a: \( 0 < x_2 < k \)
      • Dla \(y_1 = 1\) i \(y_2 = 1\) :
        \(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\)
      • Dla \(y_1 \neq 1\) i \(y_2 = 1\) :
        \(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\)
      • Dla \(y_1 = 1\) i \(y_2 \neq 1\) :
        \(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\)
      • Dla \(y_1 \neq 1\) i \(y_2 \neq 1\) to:
        \(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)\)
    • Przypadek 2b: \( x_2 \geq k \)
      • Dla \(y_1 = 1\) i \(y_2 = 1\) :
        \(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\)
      • Dla \(y_1 = 1\) i \(y_2 \neq 1\) :
        \(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\)
      • Dla \(y_1 \neq 1\) i \(y_2 = 1\) :
        \(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\)
      • Do \(y_1 \neq 1\) oraz \(y_2 \neq 1\) jest:
        \((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) \)
        Do \(y_2 = x_1+1\) z \( 2 \leq y_2 \leq k\) jest
        \(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)\) z \( 2 \leq y_1 \leq k\).
        Tutaj jest tylko jedno rozwiązanie \( (y_1, y_2) \).
        Ponieważ wybieramy \(y^*_2=y_2-1\) jako wartość, jest \(y^*_1 = y_1-(k-1) < 2\).
        Ponadto za \(y^*_2*=y_2+1\) następnie \(y^*_1 = y_1+(k-1) > k\).
  • 3. Sprawa: \( x_1 \geq k \)
    • Przypadek 3a: \( x_2 \geq k \)
      • Przypadek 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\)
        • Dla \(y_1 = 1\) i \(y_2 = 1\) :
          \(f(x_1, y_1) = f(x_1, 1) = m_1\)
          \(f(x_2, y_2) = f(x_2, 1) = m_2 = m_1\)
        • Dla \(y_1 = 1\) i \(y_2 \neq 1\) :
          \(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\)
        • Dla \(y_1 \neq 1\) i \(y_2 = 1\) :
          Zobacz \(y_1 = 1\) i \(y_2 \neq 1\) .
        • Do \(y_1 \neq 1\) oraz \(y_2 \neq 1\) jest:
          \(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)\)
          Następnie \(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)\)
          Do \(y_1 \neq y_2\) jest \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
          Do \(y_1 = y_2\) jest \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) oraz
          \(\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\) w przeciwieństwie do \(m_1 = m_2\).
      • Obudowa 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\)
        • Dla \(y_1 = 1\) i \(y_2 = 1\) :
          \(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\)
        • Dla \(y_1 = 1\) i \(y_2 \neq 1\) :
          \(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\)
        • Dla \(y_1 \neq 1\) i \(y_2 = 1\) :
          Zobacz \(y_1 = 1\) i \(y_2 \neq 1\) .
        • Do \(y_1 \neq 1\) oraz \(y_2 \neq 1\) jest:
          \(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)\)
          Następnie \(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)\)
          Do \(y_1 \neq y_2\) jest \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
          Do \(y_1 = y_2\) jest \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) oraz
          \(\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}\)
          Dobrze tam na \(2 \leq y \leq k\) zawsze \(l \in \mathbb{N}_0\), aby
          \(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
          Dowód: tam \((k-1)\) jest liczbą pierwszą, jest (z powodu lematu Bézouta)
          \((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
          do rozwiązania, ponieważ \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Dzieli \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
          To jest jedyne rozwiązanie \(l_1\), bo dla jednego
          \(l_2 = l_1 + (m_2-m_1)\) jest \( y_2 = y_1 + (k-1) > k\).

Ciekawe informacje ogólne na temat dobble i matematyki można również znaleźć tutaj lub tutaj . W poniższym skrypcie możesz zobaczyć sprawdzoną wcześniej formułę w działaniu: Dobble (dla \((k-1)\) prim) można wygenerować jednym naciśnięciem przycisku:

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

Plecy