Математика в грі Dobble03
22

На нашому останньому сімейному ігровому вечорі діти з ентузіазмом дістали гру Dobble (видання про Гаррі Поттера). Програвши п'ять раундів (моя карта не збігалася з ігровою картою), я з подивом дізнався, що кожен гравець завжди може знайти пару в кожному раунді. Однак моє здивування призвело лише до більшої кількості програних раундів – діти просто були швидшими.

Достатня причина, щоб ближче поглянути на гру з математичної точки зору. Спочатку принцип гри: Dobble – це проста карткова гра з $55$ круглими картами, кожна з яких показує вісім різних символів. Усі карти роздаються по черзі, залишаючи лише останню карту в середині столу. Тепер усі гравці повинні одночасно порівняти символи на карті з символами на своїй поточній верхній карті. Якщо гравець знайшов той самий символ на обох картах, він може покласти свою карту в стопку, найшвидше назвавши символ. Виграє той гравець, який першим скине всі свої карти.

Як це може бути, що існує $55$ таких карток, які були побудовані таким чином, що будь-які 2 карти мають рівно один спільний символ? Яка мінімальна кількість таких символів повинна бути використана? Яка максимальна кількість таких карток?

Спочатку ми створюємо ці картки, використовуючи наступні логічні кроки (всі згодом створені картки мають властивість, що вони сортуються в порядку зростання): Перша карта повинна мати 8 різних символів, тобто читання:

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

Як нам скласти наступні карти так, щоб вони мали рівно один спільний символ з першою картою?:

Тут уже можна побудувати будь-яку кількість таких карток (ви просто заповнюєте місця в порядку зростання, починаючи з $9$ ). Але цей тривіальний випадок нецікавий, оскільки нас цікавить набір з мінімальною кількістю символів (і максимальною кількістю карток). Тепер розглянемо другий символ $ x_{l.2} $ кожної картки, для якого, очевидно, має застосовуватися наступне: $ x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} $ . Тому ми обов'язково ввели $ k $ нових символів. Але тепер $ k \leq 8-1 = 7 $ , оскільки жоден із символів \ $ 7 $ $ x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} $ (крайньої лівої карти) може збігатися з другим символом кожної з інших карт (інакше було б два однакових символу ).

Ми знайшли максимум з цих 7 нових карток:

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

З тим же аргументом ми зараз будуємо наступні карти $7$ (перша з цих карт має зіткнутися з нашою початковою картою, а не з $1$ , інакше вона буде з $7$ раніше знайшли карти):

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

Цей аргумент можна продовжити для наступних $7$ карт таким самим чином; загалом у $8-2 = 6$ разів більше. Таким чином, останні $7$ карт:

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

Якби ви зараз хотіли побудувати іншу картку $$\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)$$ , це не вдасться, оскільки ця картка не мають спільного символу зі стартовою картою. Це означає, що ми створили максимум $1 + 8 \cdot 7 = 57$ карток. Зараз наша мета — побудувати стільки ж.

Для цього ми дивимося на перші 7 нових знайдених карт і приходимо до висновку, що нам конче потрібні $7 \cdot 7$ нові символи (жодна карта не може мати дублікат символу, і кожен символ, який буде надано, може не з’являтися двічі, тому що $1$ уже подвійний):

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

Це означає, що нам потрібно мінімум $8 + (7 \cdot 7) = 57$ символів (тобто стільки символів, скільки карток!). Зараз ми намагаємося обійтися цим числом і знайти специфікацію конструкції для всіх інших елементів. Для цього ми створюємо трохи менший дубль, який містить лише $3$ символів на картку, і отримуємо його як початкову картку

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

із загальною кількістю карток $ \(1 + 3 \cdot 2 = 7$ та символів $ 3 + (2 \cdot 2) = 7$ . Трохи проб і помилок (і використовуючи вже призначені символи) ви отримаєте наступний доббл:

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

Чи можна це також знайти систематично? Для цього ми вводимо знову призначені символи $4, 5, 6, 7$ у квадратну матрицю:

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

Тепер уявімо для перших двох карток (починаючи з початкових символів \ $4$ і $5$ ) вертикальні сполучні лінії до нижніх символів $6$ і $7$:

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

Оскільки ці лінії не перетинаються, ми отримуємо (накресливши символи на сполучних лініях рядок за рядком) найближчі дійсні картки:

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

Нарешті, ми уявляємо з'єднувальні лінії з іншим нахилом (у цьому випадку з нахилом $1$ ):

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

Друга сполучна лінія (між $5$ і $6$ ) виходить із матриці на правому краю та знову входить на лівому краю. Розумно вибираючи градієнт, ми гарантуємо, що з’єднувальні лінії не перетинаються одна з одною, але також і попередні (вертикальні) з’єднувальні лінії не перетинаються. Ця ідея дизайну зрештою призводить до наступної формули дизайну:

Добл з $k \in \mathbb{N} \, | \, (k-1) \text{ prim} $ має $1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)$ картки та символи. Для карти $K_x$ з $x \in \mathbb{N}$ і $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)$ частин цих карток. Тепер залишається тільки показати:

$$ \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-й випадок: $ x_1 = 0 $
- Випадок 1а: $ 0 < x_2 < k $
  - Для $y_1 = 1$ і $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$ .
  - Для $y_1 \neq 1$ і $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$
  - Для $y_1 = 1$ і $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$
  - Для $y_1 \neq 1$ і $y_2 \neq 1$ є:
    $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$
- Випадок 1b: $ x_2 \geq k $
  - Для $y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$ і $y_2 = 1$ маємо:
    $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$
  - Для $y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1$ і $y_2 = 1$ є:
    $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$
  - Для $y_2 \neq 1$ є:
    $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-й випадок: $ 0 < x_1 < k $
- Випадок 2а: $ 0 < x_2 < k $
  - Для $y_1 = 1$ і $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$
  - Для $y_1 \neq 1$ і $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$
  - Для $y_1 = 1$ і $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$
  - Для $y_1 \neq 1$ і $y_2 \neq 1$ є:
    $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)$
- Випадок 2б: $ x_2 \geq k $
  - Для $y_1 = 1$ і $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$
  - Для $y_1 = 1$ і $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$
  - Для $y_1 \neq 1$ і $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$
  - Для $y_1 \neq 1$ і $y_2 \neq 1$ є:
    $(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) $
    Для $y_2 = x_1+1$ з $ 2 \leq y_2 \leq k$ є
    $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)$ з $ 2 \leq y_1 \leq k$.
    Тут є лише одне рішення $ (y_1, y_2) $.
    Тому що ми вибираємо $y^*_2=y_2-1$ як вартість, є $y^*_1 = y_1-(k-1) < 2$.
    Крім того, для $y^*_2*=y_2+1$ потім $y^*_1 = y_1+(k-1) > k$.
3. Корпус: $ x_1 \geq k $
- Випадок 3а: $ x_2 \geq k $
  - Випадок 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$
    - Для $y_1 = 1$ і $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$
    - Для $y_1 = 1$ і $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$
    - Для $y_1 \neq 1$ і $y_2 = 1$ маємо:
      Див. $y_1 = 1$ і $y_2 \neq 1$ .
    - Для $y_1 \neq 1$ і $y_2 \neq 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) = 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)$
      Тоді $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)$
      Для $y_1 \neq y_2$ є $L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)$.
      Для $y_1 = y_2$ є $L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2$ і
      $\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$ в суперечність до $m_1 = m_2$.
  - Випадок 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$
    - Для $y_1 = 1$ і $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$
    - Для $y_1 = 1$ і $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$
    - Для $y_1 \neq 1$ і $y_2 = 1$ маємо:
      Див. $y_1 = 1$ і $y_2 \neq 1$ .
    - Для $y_1 \neq 1$ і $y_2 \neq 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) = 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)$
      Тоді $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)$
      Для $y_1 \neq y_2$ є $L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)$.
      Для $y_1 = y_2$ є $L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2$ і
      $\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}$
      Ну там за $2 \leq y \leq k$ завжди а $l \in \mathbb{N}_0$, так що
      $m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)$.
      Доказ: є $(k-1)$ є простим, є (через лему Безу)
      $(k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)$
      розв’язне, тому що $\text{ggT}\left((k-1),(m_2-m_1)\right) = 1$ Розщеплення $-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)$.
      Тоді це єдине рішення $l_1$, тому що для одного
      $l_2 = l_1 + (m_2-m_1)$ є $ y_2 = y_1 + (k-1) > k$.

Ви також можете знайти цікаву довідкову інформацію на тему доббл і математики тут або тут . У наступному скрипті ви можете побачити раніше перевірену формулу в дії: Dobbles (для $(k-1)$ prim) можна створити натисканням кнопки:

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

Математика в грі Dobble0322

Математика в грі Dobble03
22