Kumdlalo wethu wokugqibela wosapho, abantwana bakhuphe umdlalo iDobble ngomdla omkhulu (uhlelo lukaHarry Potter). Emva kokuphulukana nemijikelo emihlanu (ngaphandle kokuba ikhadi lam libonakale lifana nekhadi lokudlala), ndothuka xa ndifumanisa ukuba wonke umdlali unokufumana umdlalo kuyo yonke imijikelo. Nangona kunjalo, ukungakholelwa kwam kwadibana nemijikelo emininzi elahlekileyo - abantwana babekhawuleza nje.
Isizathu esaneleyo sokujonga ngakumbi umdlalo ngokwembono yezibalo. Okokuqala umgaqo womdlalo: IDobble ngumdlalo wekhadi olula onamakhadi arawndi \(55\) , ngalinye libonisa iisimboli ezisibhozo ezahlukeneyo. Onke amakhadi aphathwa ngokulandelelana, kushiya kuphela ikhadi lokugqibela phakathi kwetafile. Ngoku bonke abadlali kufuneka ngaxeshanye bathelekise iisimboli ekhadini kunye neempawu kwikhadi labo eliphezulu langoku. Ukuba umdlali ufumene isimboli efanayo kuwo omabini amakhadi, unokubeka ikhadi lakhe kwisitaki ngokuba ngoyena ukhawulezayo ukubiza isimboli. Umdlali olahla onke amakhadi abo kuqala uphumelele.
Kwenzeka njani ukuba kukho amakhadi \(55\) anjalo akhiwe ngendlela yokuba nawaphi na amakhadi ama-2 abe nesimboli enye kanye ngokufanayo? Leliphi inani elincinane leempawu ezinjalo ekufuneka zisetyenziswe? Lithini inani eliphezulu lamakhadi anjalo?
Okokuqala, sakha la makhadi sisebenzisa la manyathelo alandelayo anengqiqo (onke amakhadi akhiwe emva koko anepropathi ehlelwe ngokomyalelo onyukayo): Ikhadi lokuqala kufuneka libe neesimboli ezisi-8 ezahlukeneyo, o.k.:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Sizakha njani la makhadi alandelayo ukuze abe nophawu olunye 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)$$
Naliphi na inani lalo makhadi asenokwakhiwa apha (ugcwalisa ngokulula iindawo ngolandelelwano olunyukayo, ukuqala ngo \(9\) ). Eli tyala lincinci alinamdla, nangona kunjalo, kuba sinomdla kwiseti enenani elincinci leempawu (kunye nenani eliphezulu lamakhadi). Ngoku siqwalasela isimboli sesibini \( x_{l.2} \) yekhadi ngalinye, ngokucacileyo oku kulandelayo kufuneka kusebenze: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) Ke ngoko kufuneka sazise \( k \) iisimboli ezintsha. Kodwa ngoku \( k \leq 8-1 = 7 \) , ekubeni akukho nanye \( 7 \) \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (kwelona khadi lisekhohlo) linokutshatisa isimboli sesibini sekhadi ngalinye (kungenjalo kuya kubakho iisimboli ezimbini ezifanayo ).
Sifumene ubuninzi kula makhadi asi-7 matsha:
$$\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)$$
Kwale ngxoxo inye ngoku sakha iimephu ezilandelayo \(7\) (eyokuqala kwezi mephu kufuneka ingqubane nemephu yethu yokuqalisa, kwaye hayi nge \(1\) , kungenjalo iyakuba nge \(7\) ngaphambili. ufumene iimephu):
$$\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 ngxoxo ingaqhubeka kumakhadi alandelayo \(7\) ngendlela efanayo; iyonke iphindwe ka- \(8-2 = 6\) ngaphezulu. Amakhadi okugqibela \(7\) ke ngoko:
$$\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)$$
Ukuba ngoku ubufuna ukwakha 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)$$ ube nesimboli eqhelekileyo enekhadi lokuqala. Oku kuthetha ukuba sakhe ubuninzi \(1 + 8 \cdot 7 = 57\) amakhadi. Injongo yethu ngoku kukwakha ezininzi.
Ukwenza oku, sijonga amakhadi amatsha angama-7 okuqala afunyenweyo kwaye sifikelela kwisigqibo sokuba sidinga ngokupheleleyo \(7 \cdot 7\) iisimboli ezintsha (akukho khadi linokuba nesimboli ephindiweyo kwaye isimboli ngasinye esiya kunikezelwa sinokuvela kabini ngenxa yokuba \(1\) sele iphindwe kabini):
$$\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)$$
Oku kuthetha ukuba sifuna ubuncinane \(8 + (7 \cdot 7) = 57\) iisimboli (okt. iisimboli ezininzi njengamakhadi!). Ngoku sizama ukuphumelela ngeli nani kwaye sifumane iinkcukacha zoyilo zazo zonke ezinye izinto. Ukwenza oku, sakha idobble encinci kancinane ethwala kuphela iisimboli \(3\) zekhadi kwaye ufumane njengekhadi lokuqala.
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
kunye 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)$$
ngetotali \(1 + 3 \cdot 2 = 7\) amakhadi kunye \( 3 + (2 \cdot 2) = 7\) iisimboli. Ngolingo oluncinci kunye nempazamo (kunye nokusebenzisa iisimboli esele zabelwe) ufumana le dobble ilandelayo:
$$\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)$$
Ngaba oku kunokufumaneka ngokucwangcisiweyo? Ukwenza oku, singenisa iisimboli ezisanda kwabelwe \(4, 5, 6, 7\) kwisikwere sematriki.:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Ngoku sicingela amakhadi amabini okuqala (ukuqala ngeesimboli zokuqala \ \(4\) kunye \(5\) ) imigca eqhagamshelayo ethe nkqo kwiisimboli ezisezantsi \(6\) kunye \(7\):
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Ekubeni le migca ingadibanisi, sifumana (ngokucwangcisa iisimboli kumgca wokudibanisa ngomgca) awona makhadi asondeleyo asemthethweni.:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Okokugqibela, sicinga ukudibanisa imigca kunye nethambeka elahlukileyo (kulo mzekelo kunye nethambeka \(1\) ):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
Umgca wesibini wokudibanisa (phakathi \(5\) kunye \(6\) ) ushiya i-matrix kumda wasekunene kwaye uphinde ungene kumda wasekhohlo. Ngokukhetha ngobuchule i-gradient, siqinisekisa ukuba imigca yokudibanisa ayiphambanisi, kodwa kwakhona ukuba imigca yangaphambili (ethe nkqo) yokudibanisa ayiphambanisi. Le ngcamango yoyilo ekugqibeleni ikhokelela kwifomula yoyilo ilandelayo:
Idoboli eline \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) ine \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) amakhadi kunye neempawu. \(K_x\) nge \(x \in \mathbb{N}\) kunye \(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.$$
Kukho \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) amaqhekeza ala makhadi. Ngoku kushiyeke kuphela ukubonisa:
$$ \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) $$
- Ityala lokuqala: \( x_1 = 0 \)
- Ityala 1a: \( 0 < x_2 < k \)
- Kuba \(y_1 = 1\) kunye \(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\) kunye \(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\) - Kwi \(y_1 = 1\) kunye \(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\) - Kuba \(y_1 \neq 1\) kunye \(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\)
- Kuba \(y_1 = 1\) kunye \(y_2 = 1\) :
- Ityala 1b: \( x_2 \geq k \)
- Ku \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kunye \(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\) - Kuba \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kunye \(y_2 = 1\) yile:
\(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\) - Ye \(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 \)
- Ku \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kunye \(y_2 = 1\) :
- Ityala 1a: \( 0 < x_2 < k \)
- Ityala lesibini: \( 0 < x_1 < k \)
- Ityala 2a: \( 0 < x_2 < k \)
- Kuba \(y_1 = 1\) kunye \(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\) kunye \(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\) - Kwi \(y_1 = 1\) kunye \(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\) - Kuba \(y_1 \neq 1\) kunye \(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)\)
- Kuba \(y_1 = 1\) kunye \(y_2 = 1\) :
- Ityala 2b: \( x_2 \geq k \)
- Kuba \(y_1 = 1\) kunye \(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\) - Kwi \(y_1 = 1\) kunye \(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\) kunye \(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\) - Kuba \(y_1 \neq 1\) kwaye \(y_2 \neq 1\) yi:
\((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) \)
Kuba \(y_2 = x_1+1\) kunye \( 2 \leq y_2 \leq k\) yi
\(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)\) kunye \( 2 \leq y_1 \leq k\).
Sinye kuphela isisombululo apha \( (y_1, y_2) \).
Ngenxa yokuba sikhetha \(y^*_2=y_2-1\) njengexabiso, liyi \(y^*_1 = y_1-(k-1) < 2\).
Ukongeza, kuba \(y^*_2*=y_2+1\) ngoko \(y^*_1 = y_1+(k-1) > k\).
- Kuba \(y_1 = 1\) kunye \(y_2 = 1\) :
- Ityala 2a: \( 0 < x_2 < k \)
- 3. Ityala: \( x_1 \geq k \)
- Ityala 3a: \( x_2 \geq k \)
- Ityala 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\)
- Kuba \(y_1 = 1\) kunye \(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\) - Kwi \(y_1 = 1\) kunye \(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\) kunye \(y_2 = 1\) :
Bona \(y_1 = 1\) kunye \(y_2 \neq 1\) . - Kuba \(y_1 \neq 1\) kwaye \(y_2 \neq 1\) yi:
\(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)\)
Emva koko \(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)\)
Kuba \(y_1 \neq y_2\) yi \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Kuba \(y_1 = y_2\) yi \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) kwaye
\(\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\) ngokuchaseneyo ne \(m_1 = m_2\).
- Kuba \(y_1 = 1\) kunye \(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\)
- Kuba \(y_1 = 1\) kunye \(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\) - Kwi \(y_1 = 1\) kunye \(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\) kunye \(y_2 = 1\) :
Bona \(y_1 = 1\) kunye \(y_2 \neq 1\) . - Kuba \(y_1 \neq 1\) kwaye \(y_2 \neq 1\) yi:
\(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)\)
Emva koko \(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)\)
Kuba \(y_1 \neq y_2\) yi \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Kuba \(y_1 = y_2\) yi \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) kwaye
\(\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}\)
Kulungile apho \(2 \leq y \leq k\) rhoqo a \(l \in \mathbb{N}_0\), lo nto
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Bungqina: khona \((k-1)\) yeyona nto iphambili, 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)\)
inokusombulula, kuba \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Ukwahlula \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
Emva koko oku kuphela kwesisombululo \(l_1\), ngenxa yokuba enye
\(l_2 = l_1 + (m_2-m_1)\) yi \( y_2 = y_1 + (k-1) > k\).
- Kuba \(y_1 = 1\) kunye \(y_2 = 1\) :
- Ityala 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\)
- Ityala 3a: \( x_2 \geq k \)
Unokufumana kwakhona ulwazi olunomdla lwemvelaphi kwisihloko se-dobble kunye nemathematika apha okanye apha . Kolu shicilelo lulandelayo ungabona ifomula engqiniweyo yangaphambili isebenza: IiDobbles (ye \((k-1)\) prim) zinokuveliswa ngokucofa iqhosha.:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.