Математика в игре Доббль

На последнем семейном вечере дети с энтузиазмом принесли к столу игру Доббл (в версии Гарри Поттера). После 5-го проигрышного раунда (без видимого попадания моей карты в игральную карту) мне, к моему удивлению, сказали, что каждый игрок всегда может найти попадание в каждом раунде. Но мое недоверие подтвердилось лишь дальнейшими пропущенными кругами — дети просто были быстрее.


Достаточно причин, чтобы поближе взглянуть на игру с математической точки зрения. Во-первых, принцип игры: Доббл — это простая карточная игра с \(55\) круглыми картами, на каждой из которых изображено восемь различных символов. Все карты раздаются по очереди, оставляя только последнюю карту в середине стола. Теперь все игроки должны одновременно сравнивать символы на карте с символами на их текущей верхней карте. Если игрок нашел одинаковый символ на обеих картах, он может поместить свою карту в стопку, назвав этот символ быстрее всех. Выигрывает игрок, первым сбросивший все свои карты.

Как могло случиться, что существуют \(55\) таких карт, составленных таким образом, что любые две карты имеют ровно один общий символ? Какое минимальное количество таких символов необходимо использовать? Какое максимальное количество таких карт?

Сначала мы конструируем эти карты, используя следующие логические шаги (все впоследствии построенные карты имеют свойство сортироваться по возрастанию): Первая карта должна иметь 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\)
    • Случай 1б: \( 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 \)
      • Случай 3а': \(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\).
      • Случай 3а'': \(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\).

Вы также можете найти интересную справочную информацию по теме доббла и математики здесь или здесь . В следующем сценарии вы можете увидеть проверенную ранее формулу в действии: Добблы (для \((k-1)\) prim) можно генерировать нажатием кнопки.:

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

Назад