На останньому сімейному вечорі діти з ентузіазмом винесли на стіл гру « Доббл» (у виданні «Гаррі Поттер»). Після 5-го програного раунду (без видимого попадання моєї карти гральною картою) мені, на мій подив, сказали, що кожен гравець завжди може знайти влучення в кожному раунді. Але мою недовіру визнали лише подальші втрачені кола – діти були просто швидше.
Достатня причина, щоб ближче поглянути на гру з математичної точки зору. Спочатку принцип гри: Dobble – це проста карткова гра з \(55\) круглими картами, кожна з яких показує вісім різних символів. Усі карти роздаються по черзі, залишаючи лише останню карту в середині столу. Тепер усі гравці повинні одночасно порівняти символи на карті з символами на своїй поточній верхній карті. Якщо гравець знайшов той самий символ на обох картах, він може покласти свою карту в стопку, найшвидше назвавши символ. Виграє той гравець, який першим скине всі свої карти.
Як може бути, що існує \(55\) таких карт, які були побудовані таким чином, що будь-які 2 карти мають рівно один спільний символ? Яку мінімальну кількість таких символів необхідно використовувати? Яка максимальна кількість таких карток?
Спочатку ми створюємо ці картки, використовуючи наступні логічні кроки (всі згодом створені картки мають властивість, що вони сортуються в порядку зростання): Перша карта повинна мати 8 різних символів, тобто читання:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Тепер ми побудуємо наступні картки таким чином, щоб вони мали рівно один спільний символ з першою карткою:
$$\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)$$
Тут уже можна побудувати будь-яку кількість таких карток (ви просто заповнюєте місця в порядку зростання, починаючи з \(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\)
- Для \(y_1 = 1\) і \(y_2 = 1\) маємо:
- Випадок 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 \)
- Для \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) і \(y_2 = 1\) маємо:
- Випадок 1а: \( 0 < x_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)\)
- Для \(y_1 = 1\) і \(y_2 = 1\) маємо:
- Випадок 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\).
- Для \(y_1 = 1\) і \(y_2 = 1\) маємо:
- Випадок 2а: \( 0 < x_2 < 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\).
- Для \(y_1 = 1\) і \(y_2 = 1\) маємо:
- Випадок 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\).
- Для \(y_1 = 1\) і \(y_2 = 1\) маємо:
- Випадок 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\)
- Випадок 3а: \( x_2 \geq k \)
Ви також можете знайти цікаву довідкову інформацію на тему доббл і математики тут або тут . У наступному скрипті ви можете побачити раніше перевірену формулу в дії: Dobbles (для \((k-1)\) prim) можна створити натисканням кнопки:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.