Son aile oyun gecemizde çocuklar büyük bir coşkuyla Dobble oyununu (Harry Potter versiyonu) ortaya çıkardılar. Beş tur kaybettikten sonra (kartımın oyun kartıyla görünürde eşleşmemesi üzerine), her oyuncunun her turda mutlaka bir eşleşme bulabileceğini öğrenince şaşırdım. Ancak, şaşkınlığım daha fazla tur kaybetmemle sonuçlandı – çocuklar daha hızlıydı.
Oyuna matematiksel bir bakış açısıyla daha yakından bakmak için yeterli sebep. İlk olarak oyun prensibi: Dobble, her biri sekiz farklı sembol gösteren \(55\) yuvarlak kartlardan oluşan basit bir kart oyunudur. Tüm kartlar sırayla dağıtılır ve masanın ortasında yalnızca son kart bırakılır. Artık tüm oyuncuların karttaki sembolleri mevcut en üstteki karttaki sembollerle aynı anda karşılaştırması gerekiyor. Bir oyuncu her iki kartta da aynı sembolü bulursa, sembolü en hızlı isimlendirerek kartını desteye yerleştirebilir. Tüm kartlarını ilk önce atan oyuncu kazanır.
Nasıl olur da herhangi 2 kartın tam olarak bir ortak sembolü olacak şekilde oluşturulmuş \(55\) kart olabilir? Kullanılması gereken bu tür sembollerin minimum sayısı nedir? Bu tür kartların maksimum sayısı nedir?
İlk olarak, aşağıdaki mantıksal adımları kullanarak bu kartları oluşturuyoruz (sonradan oluşturulan tüm kartlar, artan düzende sıralanma özelliğine sahiptir): İlk kartta 8 farklı sembol olmalıdır, yani okur:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Aşağıdaki kartları, ilk kartla tam olarak bir ortak sembole sahip olacak şekilde nasıl oluştururuz?:
$$\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)$$
Burada herhangi bir sayıda bu tür kartlar oluşturulabilir (yerleri \(9\) ile başlayarak artan sırada doldurmanız yeterlidir). Ancak, minimum sayıda sembol (ve maksimum sayıda kart) içeren bir setle ilgilendiğimiz için bu önemsiz durum ilgi çekici değildir. Şimdi her kartın ikinci sembolünü \( x_{l.2} \) ele alacağız ve bunun için aşağıdakilerin geçerli olması gerektiği açıktır: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . Bu nedenle, zorunlu olarak \( k \) yeni semboller getirdik. Ama şimdi \( k \leq 8-1 = 7 \) , çünkü \( 7 \) sembollerinin hiçbiri \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (en soldaki karttan) diğer kartların her birinin ikinci sembolüyle eşleşebilir (aksi takdirde iki özdeş sembol olurdu) ).
Bu 7 yeni karttan maksimumunu bulduk:
$$\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)$$
Aynı argümanla şimdi sonraki \(7\) haritalarını oluşturuyoruz (bu haritaların ilki başlangıç haritamızla çarpışmalıdır, \(1\) ile değil, aksi takdirde önceden \(7\) ile olurdu) bulunan haritalar):
$$\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)$$
Bu argüman, sonraki \(7\) kart için de aynı şekilde devam ettirilebilir; toplamda \(8-2 = 6\) kez daha. Bu nedenle son \(7\) kart şöyledir::
$$\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)$$
Şimdi başka bir 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)$$ , bu kartta bulunmadığından bu başarısız olur. başlangıç kartıyla ortak bir sembol. Bu, maksimum \(1 + 8 \cdot 7 = 57\) kart oluşturduğumuz anlamına gelir. Şimdiki hedefimiz bir o kadarını inşa etmek.
Bunu yapmak için, bulunan ilk 7 yeni karta bakarız ve \(7 \cdot 7\) yeni sembollere kesinlikle ihtiyacımız olduğu sonucuna varırız (hiçbir kartın kopya sembolü olamaz ve verilecek her sembol \(1\) zaten çift olduğundan iki kez görünmeyebilir):
$$\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)$$
Bu, minimum \(8 + (7 \cdot 7) = 57\) sembole (yani kart sayısı kadar sembol!) ihtiyacımız olduğu anlamına gelir. Şimdi bu sayıyla yetinmeye ve diğer tüm unsurlar için bir tasarım özelliği bulmaya çalışıyoruz. Bunu yapmak için, kart başına yalnızca \(3\) sembol taşıyan biraz daha küçük bir dobble oluşturuyoruz ve başlangıç kartı olarak alıyoruz
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
ve diğer kartlar
$$\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)$$
toplam \(1 + 3 \cdot 2 = 7\) kartları ve \( 3 + (2 \cdot 2) = 7\) sembolleri ile. Biraz deneme yanılma ile (ve önceden atanmış sembolleri kullanarak) aşağıdaki dobble'ı elde edersiniz:
$$\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)$$
Bu da sistematik olarak bulunabilir mi? Bunu yapmak için, yeni atanan sembolleri \(4, 5, 6, 7\) kare bir matrise giriyoruz.:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Şimdi ilk iki kart için (başlangıç sembolleri \ \(4\) ve \(5\) ile başlayarak) alt sembollere \(6\) ve \(7\) ) dikey bağlantı çizgilerini hayal ediyoruz.:
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Bu çizgiler kesişmediği için (bağlantı hatlarındaki sembolleri satır satır çizerek) en yakın geçerli kartları elde ederiz.:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Son olarak, farklı bir eğime sahip çizgileri birleştirmeyi hayal ediyoruz (bu durumda eğim \(1\) ile):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
İkinci bağlantı hattı ( \(5\) ve \(6\) arasında) matrisi sağ kenardan bırakır ve sol kenardan tekrar girer. Degradeyi akıllıca seçerek, bağlantı çizgilerinin birbiriyle kesişmemesini, aynı zamanda önceki (dikey) bağlantı çizgilerinin de kesişmemesini sağlıyoruz. Bu tasarım fikri sonuçta aşağıdaki tasarım formülüne yol açar:
\(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) ile bir dobble \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) değerine sahiptir \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) kartlar ve semboller. \(x \in \mathbb{N}\) ve \(0 \leq x \leq (k-1) \cdot k\) olan \(K_x\) haritası için geçerlidir:
$$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.$$
Bu kartlardan \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) adet bulunmaktadır. Şimdi sadece göstermek için kalır:
$$ \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. durum: \( x_1 = 0 \)
- Durum 1a: \( 0 < x_2 < k \)
- \(y_1 = 1\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 = 1\) için:
- Durum 1b: \( x_2 \geq k \)
- \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 = 1\) için:
\(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\) için:
\(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\) ve \(y_2 = 1\) için:
- Durum 1a: \( 0 < x_2 < k \)
- 2. durum: \( 0 < x_1 < k \)
- Durum 2a: \( 0 < x_2 < k \)
- \(y_1 = 1\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 = 1\) için:
- Durum 2b: \( x_2 \geq k \)
- \(y_1 = 1\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 = 1\) için:
\(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\) - İçin \(y_1 \neq 1\) ve \(y_2 \neq 1\) dır-dir:
\((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) \)
İçin \(y_2 = x_1+1\) ile birlikte \( 2 \leq y_2 \leq k\) dır-dir
\(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)\) ile birlikte \( 2 \leq y_1 \leq k\).
Burada tek bir çözüm var \( (y_1, y_2) \).
Çünkü biz seçiyoruz \(y^*_2=y_2-1\) değer olarak, \(y^*_1 = y_1-(k-1) < 2\).
Ayrıca, için \(y^*_2*=y_2+1\) sonra \(y^*_1 = y_1+(k-1) > k\).
- \(y_1 = 1\) ve \(y_2 = 1\) için:
- Durum 2a: \( 0 < x_2 < k \)
- 3. Vaka: \( x_1 \geq k \)
- Durum 3a: \( x_2 \geq k \)
- Durum 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\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 = 1\) için:
Bkz. \(y_1 = 1\) ve \(y_2 \neq 1\) . - İçin \(y_1 \neq 1\) ve \(y_2 \neq 1\) dır-dir:
\(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)\)
Sonra \(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)\)
İçin \(y_1 \neq y_2\) dır-dir \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
İçin \(y_1 = y_2\) dır-dir \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) ve
\(\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\) aykırı olarak \(m_1 = m_2\).
- \(y_1 = 1\) ve \(y_2 = 1\) için:
- Vaka 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\) ve \(y_2 = 1\) için:
\(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\) ve \(y_2 \neq 1\) için:
\(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\) ve \(y_2 = 1\) için:
Bkz. \(y_1 = 1\) ve \(y_2 \neq 1\) . - İçin \(y_1 \neq 1\) ve \(y_2 \neq 1\) dır-dir:
\(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)\)
Sonra \(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)\)
İçin \(y_1 \neq y_2\) dır-dir \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
İçin \(y_1 = y_2\) dır-dir \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) ve
\(\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}\)
Iyi orada \(2 \leq y \leq k\) her zaman bir \(l \in \mathbb{N}_0\), Böylece
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Kanıt: orada \((k-1)\) asaldır (Bézout'un lemmasından dolayı)
\((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
çözülebilir, çünkü \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Bölmeler \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
O zaman tek çözüm bu \(l_1\), çünkü biri için
\(l_2 = l_1 + (m_2-m_1)\) dır-dir \( y_2 = y_1 + (k-1) > k\).
- \(y_1 = 1\) ve \(y_2 = 1\) için:
- Durum 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\)
- Durum 3a: \( x_2 \geq k \)
Ayrıca burada veya burada dobble ve matematik konusuyla ilgili ilginç arka plan bilgileri bulabilirsiniz. Aşağıdaki komut dosyasında önceden kanıtlanmış formülü çalışırken görebilirsiniz: Dobbles (for \((k-1)\) prim) bir düğmeye basılarak oluşturulabilir:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.