ゲームの数学Dobble

最後の家族の夜に、ゲームDobble (Harry Potter Edition)が子供たちによって熱狂的にテーブルに運ばれました。 5回目の敗北(トランプで私のカードの目に見えるヒットがない)の後、私は驚いたことに、すべてのプレーヤーがすべてのラウンドで常にヒットを見つけることができると言われました。 しかし、私の不信はさらにラップを失ったことでのみ認められました-子供たちは単に速くなりました。


数学的な観点からゲームを詳しく見るのに十分な理由。 最初のゲームの原則:Dobbleは、 \(55\)の丸いカードを使用した単純なカードゲームで、それぞれに8つの異なるシンボルが表示されます。 すべてのカードが順番に配られ、テーブルの真ん中に最後のカードだけが残ります。 これで、すべてのプレーヤーは、カードのシンボルを現在のトップカードのシンボルと同時に比較する必要があります。 プレイヤーが両方のカードで同じシンボルを見つけた場合、そのシンボルに名前を付けるのが最も速いことで、自分のカードをスタックに置くことができます。 最初にすべてのカードを捨てたプレイヤーが勝ちます。

2枚のカードに共通するシンボルが1つだけになるように構成された\(55\)のようなカードがあるのはどうしてですか? 使用しなければならないそのような記号の最小数はいくつですか? そのようなカードの最大数はいくつですか?

まず、次の論理的な手順を使用してこれらのカードを作成します(その後に作成されるすべてのカードには、昇順で並べ替えられるというプロパティがあります)。最初のカードには8つの異なる記号が必要です。つまり、次のようになります。:

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

次のカードは、最初のカードと共通するシンボルが1つだけになるように作成します。:

$$\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\)から始めて、昇順で場所を入力するだけです)。 ただし、この些細なケースは、シンボルの数が最小(カードの数が最大)のセットに関心があるため、面白くありません。 ここで、各カードの2番目の記号\( 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} \) (左端のカードの)は、他の各カードの2番目の記号と一致する場合があります(そうでない場合、2つの同一の記号があります) )。

これらの新しいカードを最大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\)の新しいシンボルが絶対に必要であるという結論に達します(カードに2回シンボルを含めることはできず、割り当てられる各シンボルは表示されないようにする必要があります) 2回、 \(1\)はすでに2倍になっているので):

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

ここで、最初の2枚のカード(開始記号\ \(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}$$

2番目の接続線( \(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 \)
    • ケース1a: \( 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 \)
    • ケース2a: \( 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)\)
    • ケース2b: \( 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\).
        ここに解決策は1つだけです \( (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 \)
    • ケース3a: \( 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\).

また、ここまたはここで、ドブルと数学のトピックに関する興味深い背景情報を見つけることができます。 次のスクリプトでは、以前に証明された式の動作を確認できます。ボタンを押すだけでドブル( \((k-1)\) primの場合)を生成できます。:

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

バック