Ngobusuku bokugcina bomndeni, umdlalo we- Dobble (ku-Harry Potter Edition) walethwa ngentshiseko etafuleni yizingane. Ngemuva komjikelezo wesi-5 olahlekile (ngaphandle kokushaya okubonakalayo kwekhadi lami ngekhadi lokudlala) ngatshelwa, ngokumangala kwami, ukuthi wonke umdlali angathola njalo ukushaya kuwo wonke umzuliswano. Kodwa ukungakholwa kwami kwavunywa kuphela ngokulahleka okwengeziwe - izingane zazishesha nje.
Isizathu esanele sokubhekisisa umdlalo ngombono wezibalo. Okokuqala isimiso somdlalo: I-Dobble ingumdlalo wamakhadi olula onamakhadi ayindilinga \(55\) , ngalinye libonisa izimpawu eziyisishiyagalombili ezihlukene. Wonke amakhadi aphathwa ngokushintshana, kusale kuphela ikhadi lokugcina phakathi netafula. Manje bonke abadlali kufanele baqhathanise kanyekanye izimpawu ezisekhadini nezimpawu ezisekhadini labo eliphezulu lamanje. Uma umdlali ethole uphawu olufanayo kuwo womabili amakhadi, angabeka ikhadi lakhe esitakini ngokuba oshesha ukubiza uphawu. Umdlali olahla wonke amakhadi akhe uyawina kuqala.
Kungenzeka kanjani ukuthi kukhona \(55\) amakhadi anjalo akhiwe ngendlela yokuthi noma yimaphi amakhadi ama-2 abe nophawu olulodwa ncamashi afana ngalo? Ingakanani inombolo encane yezimpawu ezinjalo okufanele zisetshenziswe? Ingakanani inombolo enkulu yamakhadi anjalo?
Okokuqala, sakha lawa makhadi sisebenzisa lezi zinyathelo ezinengqondo ezilandelayo (wonke amakhadi akhiwa kamuva anendawo ahlelwa ngokulandelana okukhuphukayo): Ikhadi lokuqala kufanele libe nezimpawu ezihlukene eziyi-8, okungukuthi ukufunda:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Manje sakha amakhadi alandelayo ngendlela yokuthi abe nophawu olulodwa olufana nekhadi lokuqala:
$$\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)$$
Noma iyiphi inombolo yamakhadi anjalo isingakwazi ukwakhiwa lapha (uvele ugcwalise izindawo ngohlelo olunyukayo, uqale ngo \(9\) ). Leli cala elincane alinambitheki, nokho, njengoba sinentshisekelo kusethi enenombolo encane yezimpawu (kanye nenani eliphakeme lamakhadi). Manje sicabangela uphawu lwesibili \( x_{l.2} \) lwekhadi ngalinye, okusobala ukuthi okulandelayo kufanele kusebenze kulo: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . Ngakho-ke sethule \( k \) izimpawu ezintsha. Kodwa manje \( k \leq 8-1 = 7 \) , njengoba lungekho uphawu \( 7 \) \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (ekhadini elingakwesokunxele) lingase lifane nophawu lwesibili lwekhadi ngalinye (ngaphandle kwalokho kuzoba nezimpawu ezimbili ezifanayo ).
Sithole ubuningi bamakhadi amasha angu-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)$$
Ngempikiswano efanayo manje sakha amamephu \(7\) alandelayo (owokuqala kulawa mamephu kufanele angqubuzane nemephu yethu yokuqala, hhayi no- \(1\) , ngaphandle kwalokho bekuzoba ne- \(7\) ngaphambilini. thola amamephu):
$$\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)$$
Le mpikiswano ingaqhutshekwa futhi kumakhadi \(7\) alandelayo; Isamba \(8-2 = 6\) izikhathi ezengeziwe. Amakhadi \(7\) wokugcina ahambisana kahle:
$$\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)$$
Uma ubungangeza elinye ikhadi $$\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)$$ izohluleka ngenxa yokuthi leli khadi alinalo uphawu nekhadi lokuqala. Sakhe inani eliphezulu \(1 + 8 \cdot 7 = 57\) lamamephu. Umgomo wethu manje uwukwakha okungenani amaningi.
Ukuze senze lokhu, sibheka amakhadi amasha ayi-7 okuqala atholiwe futhi sifinyelela esiphethweni sokuthi sidinga ngokuphelele \(7 \cdot 7\) izimpawu ezintsha lapha (akukho khadi elingase libe nophawu kabili futhi uphawu ngalunye oluzonikezwa akumele luvele. kabili, kusukela lapho \(1\) esekukabili):
$$\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)$$
Ngakho-ke sidinga okuncane \(8 + (7 \cdot 7) = 57\) izimpawu (kangangokuthi izimpawu eziningi njengamakhadi!). Manje sizama ukudlula ngale nombolo futhi sithole umthetho wokwakha wazo zonke ezinye izakhi. Ukwenza lokhu, sakha i-dobble encane kancane enezimpawu \(3\) kuphela ngekhadi ngalinye futhi siyithola njengekhadi lokuqala.
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
kanye namanye amakhadi
$$\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)$$
nesamba \(1 + 3 \cdot 2 = 7\) amakhadi kanye \( 3 + (2 \cdot 2) = 7\) izimpawu. Ngokuzama okuncane kanye nephutha (kanye nokusebenzisa izimpawu esezinikeziwe) uthola i-dobble elandelayo:
$$\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)$$
Ingabe lokhu nakho kungatholakala ngokuhlelekile? Ukwenza lokhu, sifaka izimpawu ezisanda kunikezwa \(4, 5, 6, 7\) ku-matrix yesikwele.:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Manje sicabanga ngamakhadi amabili okuqala (kusukela ngezimpawu zokuqala \ \(4\) kanye \(5\) ) imigqa yokuxhuma eqondile ezimpawu eziphansi \(6\) kanye \(7\):
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Njengoba le migqa ingaphambanisi, sithola (ngokuhlela izimpawu emigqeni yokuxhuma umugqa ngomugqa) amakhadi aseduze avumelekile.:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Okokugcina, sicabanga ukuxhuma imigqa ngomthambeka ohlukile (kulokhu ngomthambeka \(1\) ):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
Ulayini wokuxhuma wesibili (phakathi kuka- \(5\) kanye no- \(6\) ) ushiya i-matrix emaphethelweni angakwesokudla bese ungena kabusha onqenqemeni lwesokunxele. Ngokukhetha ngobuchule umthambeko, siqinisekisa ngakolunye uhlangothi ukuthi imigqa yokuxhuma ayiphambanisi, kodwa futhi ukuthi imigqa yokuxhuma yangaphambilini (eqondile) ayiphambani. Lo mbono wokuklama ekugcineni uholela kufomula yokuklama elandelayo:
I-dobble ethi \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) ine \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) amakhadi nezimpawu. \(K_x\) ethi \(x \in \mathbb{N}\) kanye \(0 \leq x \leq (k-1) \cdot k\) iyasebenza:
$$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.$$
Kukhona \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) izingcezu zalawa makhadi. Manje kusasele kuphela ukukhombisa:
$$ \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) $$
- Icala lokuqala: \( x_1 = 0 \)
- Icala 1a: \( 0 < x_2 < k \)
- Ku \(y_1 = 1\) kanye \(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\) . - Ku \(y_1 \neq 1\) kanye \(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\) - Ku \(y_1 = 1\) kanye \(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\) - Ngokuba \(y_1 \neq 1\) kanye \(y_2 \neq 1\) ithi:
\(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\)
- Ku \(y_1 = 1\) kanye \(y_2 = 1\) :
- Icala 1b: \( x_2 \geq k \)
- Okwe \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kanye \(y_2 = 1\) sine:
\(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\) - Okwe \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kanye \(y_2 = 1\) ithi:
\(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\) - Ngokuba \(y_2 \neq 1\) ithi:
\(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 \)
- Okwe \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kanye \(y_2 = 1\) sine:
- Icala 1a: \( 0 < x_2 < k \)
- Icala lesibili: \( 0 < x_1 < k \)
- Icala 2a: \( 0 < x_2 < k \)
- Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 \neq 1\) kanye \(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\) - Ku \(y_1 = 1\) kanye \(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\) - Ngokuba \(y_1 \neq 1\) kanye \(y_2 \neq 1\) ithi:
\(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)\)
- Ku \(y_1 = 1\) kanye \(y_2 = 1\) :
- Icala 2b: \( x_2 \geq k \)
- Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 \neq 1\) kanye \(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\) - Ngoba \(y_1 \neq 1\) futhi \(y_2 \neq 1\) kuyinto:
\((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) \)
Ngoba \(y_2 = x_1+1\) nge \( 2 \leq y_2 \leq k\) kuyinto
\(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)\) nge \( 2 \leq y_1 \leq k\).
Kunesixazululo esisodwa kuphela lapha \( (y_1, y_2) \).
Ngoba siyakhetha \(y^*_2=y_2-1\) njengoba value, kuyinto \(y^*_1 = y_1-(k-1) < 2\).
Ngaphezu kwalokho, for \(y^*_2*=y_2+1\) ke \(y^*_1 = y_1+(k-1) > k\).
- Ku \(y_1 = 1\) kanye \(y_2 = 1\) :
- Icala 2a: \( 0 < x_2 < k \)
- 3. Icala: \( x_1 \geq k \)
- Icala 3a: \( x_2 \geq k \)
- Icala 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\)
- Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 \neq 1\) kanye \(y_2 = 1\) :
Bona \(y_1 = 1\) kanye \(y_2 \neq 1\) . - Ngoba \(y_1 \neq 1\) futhi \(y_2 \neq 1\) kuyinto:
\(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)\)
Ngemuva kwalokho \(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)\)
Ngoba \(y_1 \neq y_2\) kuyinto \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Ngoba \(y_1 = y_2\) kuyinto \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) futhi
\(\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\) ngokuphikisana ne \(m_1 = m_2\).
- Ku \(y_1 = 1\) kanye \(y_2 = 1\) :
- Icala 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\)
- Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 = 1\) kanye \(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\) - Ku \(y_1 \neq 1\) kanye \(y_2 = 1\) :
Bona \(y_1 = 1\) kanye \(y_2 \neq 1\) . - Ngoba \(y_1 \neq 1\) futhi \(y_2 \neq 1\) kuyinto:
\(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)\)
Ngemuva kwalokho \(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)\)
Ngoba \(y_1 \neq y_2\) kuyinto \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Ngoba \(y_1 = y_2\) kuyinto \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) futhi
\(\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}\)
Well lapho for \(2 \leq y \leq k\) njalo a \(l \in \mathbb{N}_0\), ukuze
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Ubufakazi: lapho \((k-1)\) iyinhloko, yi (ngenxa ye-lemma ka-Bézout)
\((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
kuxazululeka, ngoba \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Ukuhlukana \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
Khona-ke yilona kuphela ikhambi \(l_1\), ngoba munye
\(l_2 = l_1 + (m_2-m_1)\) kuyinto \( y_2 = y_1 + (k-1) > k\).
- Ku \(y_1 = 1\) kanye \(y_2 = 1\) :
- Icala 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\)
- Icala 3a: \( x_2 \geq k \)
Ungathola futhi ulwazi lwangemuva oluthakazelisayo esihlokweni se-dobble nezibalo lapha noma lapha . Kuskripthi esilandelayo ungabona ifomula efakazelwe ngaphambilini isebenza: Ama-Dobbles (ye- \((k-1)\) prim) angakhiqizwa ngokucindezela inkinobho.:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.