Xisaabta ciyaarta Dobble

Fiidkii qoyska ee ugu dambeeyay, ciyaarta Dobble (ee Harry Potter Edition) ayaa si xamaasad leh loogu keenay miiska carruurta. Ka dib wareegii 5-aad ee lumay (iyada oo aan la arki karin kaarkayga kaarka ciyaarta) waxaa la ii sheegay, yaabay, in ciyaaryahan kasta uu mar walba heli karo garaac wareeg kasta. Laakiin rumaysad la'aantayda waxa la aqoonsaday oo keliya iyada oo dhabooyin kale oo lumay - carruurtu si fudud ayay u dheereeyeen.


Sababta ku filan inaad si dhow uga fiirsato ciyaarta dhinaca xisaabta. Marka hore mabda'a ciyaarta: Dobble waa ciyaar kaar fudud oo leh \(55\) kaararka wareega, mid kastaa wuxuu muujinayaa siddeed calaamadood oo kala duwan. Dhammaan kaadhadhka markooda ayaa loo kala qaybiyaa, kaarka ugu dambeeya oo keliya ayaa miiska dhexdiisa ku yaal. Hadda ciyaartoyda oo dhan waa inay isku mar is barbar dhigaan calaamadaha kaadhka iyo calaamadaha ku yaal kaadhka sare ee hadda. Haddii ciyaaryahan uu ka helay calaamad isku mid ah labada kaarar, wuxuu dhigi karaa kaarkiisa xirmada isagoo ah kan ugu dhaqsaha badan ee magaca calaamadda. Ciyaaryahanka tuura dhammaan kaararkooda marka hore wuu guuleystaa.

Sidee bay ku noqon kartaa in ay jiraan \(55\) kaarar sidaan oo kale ah loo dhisay si ay 2 kaarba u leeyihiin hal calaamad oo sax ah? Waa imisa tirada ugu yar ee calaamadaha noocaas ah ee ay tahay in la isticmaalo? Waa imisa tirada ugu badan ee kaararka noocaas ah?

Marka hore, waxaan ku dhiseynaa kaadhadhkan anagoo adeegsanayna tillaabooyinka macquulka ah ee soo socda (dhammaan kaadhadhka la dhisay waxay leeyihiin hanti ay u kala soocaan siday u korayaan): Kaadhka kowaad waa inuu lahaadaa 8 calaamadood oo kala duwan, tusaale ahaan akhrinta:

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

Hadda waxaan u dhiseynaa kaararka soo socda si ay u leeyihiin hal calaamad oo ay wadaagaan kaarka koowaad:

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

Tiro kasta oo kaararka noocaas ah mar hore ayaa laga dhisi karaa halkan (waxaad si fudud u buuxinaysaa meelaha sida ay u korayaan, laga bilaabo \(9\) ). Si kastaba ha ahaatee, kiiskan fudud waa mid aan xiiso lahayn, si kastaba ha ahaatee, tan iyo markii aan xiisaynayso set leh tirada ugu yar ee calaamadaha (iyo tirada ugu badan ee kaararka). Waxaan hadda tixgelineynaa calaamadda labaad \( x_{l.2} \) ee kaar kasta, taaso iska cad kuwa soo socda waa in lagu dabaqo: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . Sidaa darteed waxaan si lama huraan ah u soo saarnay \( k \) calaamado cusub. Laakin hadda \( k \leq 8-1 = 7 \) , mar haddii calaamadihii \( \( 7 \) \) midkoodna \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (kaarka bidix ee ugu dambeeya) waxa laga yaabaa inuu u dhigmo calaamadda labaad ee mid kasta oo ka mid ah kaararka kale (hadii kale waxaa jiri doona laba calaamadood oo isku mid ah). ).

Waxaan helnay ugu badnaan 7-daan kaarar oo cusub:

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

Isla doodda ayaanu hadda dhisaynaa khariidadaha soo socda ee \(7\) (ka ugu horreeya ee khariidadahani waa inay ku dhacaan khariidadda bilawga ah, ee maaha inay ku dhacaan \(1\) , haddii kale waxay la mid tahay \(7\) hore. Maab la helay):

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

Dooddan ayaa sidoo kale lagu sii wadi karaa kaararka xiga ee \(7\) ; Wadarta \(8-2 = 6\) jeer ka badan. Kaararka ugu dambeeya \(7\) waa sidaas:

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

Hadii aad ku dari lahayd kaar kale $$\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)$$ wuu fashilmi doonaa sababtoo ah kaarkani lama wadaagayo calaamad kaarka bilowga. Waxaan dhisnay ugu badnaan \(1 + 8 \cdot 7 = 57\) khariidado. Hadafkayagu hadda waa inaan dhisno ugu yaraan inta badan.

Si tan loo sameeyo, waxaan eegnaa 7 kaararka cusub ee ugu horreeya ee la helay oo aan gaadhno gabagabada inaan si buuxda ugu baahannahay \(7 \cdot 7\) calaamado cusub halkan (kaar kuma yeelan karo calaamad laba jeer iyo calaamad kasta oo loo qoondeeyay waa inaysan muuqan laba jeer, tan iyo taas oo \(1\) hore u labanlaabantay):

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

Markaa waxaan u baahanahay ugu yar \(8 + (7 \cdot 7) = 57\) calaamadaha (in ka badan calaamadaha sida kaararka!). Waxaan hadda isku dayeynaa inaan ku helno lambarkan oo aan u helno xeerka dhismaha dhammaan walxaha kale. Si tan loo sameeyo, waxaan dhiseynaa doble wax yar ka yar oo leh oo kaliya \(3\) calaamado kaarkiiba waxaana u helnaa kaadhka bilowga

$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$

iyo kaadhadhka kale

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

wadar ahaan \(1 + 3 \cdot 2 = 7\) kaararka iyo \( 3 + (2 \cdot 2) = 7\) calaamadaha. Tijaabo yar iyo khalad (iyo adigoo isticmaalaya calaamadihii hore loo qoondeeyay) waxaad helaysaa dobble soo socda:

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

Tan sidoo kale ma lagu heli karaa si habaysan? Si taas loo sameeyo, waxaanu geli calaamadaha cusub ee loo qoondeeyey \(4, 5, 6, 7\) ee matrix labajibbaaran.:

$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$

Hadda waxaan qiyaasi karnaa labada kaarar ee ugu horreeya (laga bilaabo calaamadaha bilowga \ \(4\) iyo \(5\) ) xadadka isku xirka tooska ah ee calaamadaha hoose \(6\) iyo \(7\):

$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$

Maaddaama xariiqyadani aysan isdhaafin, waxaan helnaa (adigoo ku sawiraya calaamadaha xariiqda isku xirka khadka) kaararka saxda ah ee ugu dhow.:

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

Ugu dambeyntii, waxaan ku qiyaaseynaa isku xirka khadadka jiirada kale (kiiskan oo leh jiirada \(1\) ):

$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$

Xariiqda isku xirka labaad (inta u dhaxaysa \(5\) iyo \(6\) ) waxay ka tagtaa jaantuska cidhifka midigta oo dib u galaa cidhifka bidix. Iyadoo si xirfad leh loo dooranayo jiirada, waxaan hubineynaa in hal dhinac ah in xariiqyada isku xira aysan isku xirin midba midka kale, laakiin sidoo kale in xariiqyadii hore ee (tooska) ee isku xirnaanta aysan isdhaafin. Fikraddan naqshadeynta waxay ugu dambeyntii keentaa qaacidada naqshadeynta ee soo socota:

Dobble leh \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) wuxuu leeyahay \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) kaararka iyo calaamadaha. Khariidadda \(K_x\) ee leh \(x \in \mathbb{N}\) iyo \(0 \leq x \leq (k-1) \cdot k\) ayaa khuseysa:

$$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.$$

Waxaa jira qaybo ka mid ah kaararkan \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) . Hadda waxa kaliya oo hadhay in la muujiyo:

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

  • Kiiska 1aad: \( x_1 = 0 \)
    • Kiis 1a: \( 0 < x_2 < k \)
      • Wixii \(y_1 = 1\) iyo \(y_2 = 1\) u haynaa:
        \(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\) .
      • Wixii \(y_1 \neq 1\) iyo \(y_2 = 1\) u haynaa:
        \(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\)
      • Wixii \(y_1 = 1\) iyo \(y_2 \neq 1\) u haynaa:
        \(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\)
      • Waayo \(y_1 \neq 1\) iyo \(y_2 \neq 1\) waa:
        \(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\)
    • Kiis 1b: \( x_2 \geq k \)
      • Wixii \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) iyo \(y_2 = 1\) waxaan leenahay:
        \(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\)
      • Wixii \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) iyo \(y_2 = 1\) waa:
        \(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\)
      • Waayo \(y_2 \neq 1\) waa:
        \(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 \)
  • Kiiska 2aad: \( 0 < x_1 < k \)
    • Kiis 2a: \( 0 < x_2 < k \)
      • Wixii \(y_1 = 1\) iyo \(y_2 = 1\) u haynaa:
        \(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\)
      • Wixii \(y_1 \neq 1\) iyo \(y_2 = 1\) u haynaa:
        \(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\)
      • Wixii \(y_1 = 1\) iyo \(y_2 \neq 1\) u haynaa:
        \(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\)
      • Waayo \(y_1 \neq 1\) iyo \(y_2 \neq 1\) waa:
        \(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)\)
    • Kiis 2b: \( x_2 \geq k \)
      • Wixii \(y_1 = 1\) iyo \(y_2 = 1\) u haynaa:
        \(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\)
      • Wixii \(y_1 = 1\) iyo \(y_2 \neq 1\) u haynaa:
        \(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\)
      • Wixii \(y_1 \neq 1\) iyo \(y_2 = 1\) u haynaa:
        \(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\)
      • Waayo \(y_1 \neq 1\) iyo \(y_2 \neq 1\) waa:
        \((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) \)
        Waayo \(y_2 = x_1+1\) leh \( 2 \leq y_2 \leq k\) waa
        \(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)\) leh \( 2 \leq y_1 \leq k\).
        Waxaa jira hal xal oo kaliya halkan \( (y_1, y_2) \).
        Sababtoo ah waxaan dooranaa \(y^*_2=y_2-1\) sida qiimaha, waa \(y^*_1 = y_1-(k-1) < 2\).
        Intaa waxaa dheer, loogu talagalay \(y^*_2*=y_2+1\) markaas \(y^*_1 = y_1+(k-1) > k\).
  • 3. Kiis: \( x_1 \geq k \)
    • Kiis 3a: \( x_2 \geq k \)
      • Kiiska 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\)
        • Wixii \(y_1 = 1\) iyo \(y_2 = 1\) u haynaa:
          \(f(x_1, y_1) = f(x_1, 1) = m_1\)
          \(f(x_2, y_2) = f(x_2, 1) = m_2 = m_1\)
        • Wixii \(y_1 = 1\) iyo \(y_2 \neq 1\) u haynaa:
          \(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\)
        • Wixii \(y_1 \neq 1\) iyo \(y_2 = 1\) u haynaa:
          Eeg \(y_1 = 1\) iyo \(y_2 \neq 1\) .
        • Waayo \(y_1 \neq 1\) iyo \(y_2 \neq 1\) waa:
          \(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)\)
          Kadib \(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)\)
          Waayo \(y_1 \neq y_2\) waa \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
          Waayo \(y_1 = y_2\) waa \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) iyo
          \(\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\) lid ku ah \(m_1 = m_2\).
      • Kiiska 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\)
        • Wixii \(y_1 = 1\) iyo \(y_2 = 1\) u haynaa:
          \(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\)
        • Wixii \(y_1 = 1\) iyo \(y_2 \neq 1\) u haynaa:
          \(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\)
        • Wixii \(y_1 \neq 1\) iyo \(y_2 = 1\) u haynaa:
          Eeg \(y_1 = 1\) iyo \(y_2 \neq 1\) .
        • Waayo \(y_1 \neq 1\) iyo \(y_2 \neq 1\) waa:
          \(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)\)
          Kadib \(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)\)
          Waayo \(y_1 \neq y_2\) waa \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
          Waayo \(y_1 = y_2\) waa \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) iyo
          \(\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}\)
          Waa hagaag \(2 \leq y \leq k\) had iyo jeer a \(l \in \mathbb{N}_0\), sidaas darteed
          \(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
          Caddeyn: halkaas \((k-1)\) waa ra'iisul, waa (sababtoo ah Bézout's lemma)
          \((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
          la xalin karo, sababtoo ah \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Kala baxa \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
          Markaa tani waa xalka kaliya \(l_1\), sababtoo ah hal
          \(l_2 = l_1 + (m_2-m_1)\) waa \( y_2 = y_1 + (k-1) > k\).

Waxa kale oo aad ka heli kartaa macluumaad asal ah oo xiiso leh oo ku saabsan mawduuca dobble iyo xisaabta halkan ama halkan . Qoraalkan soo socda waxaad ku arki kartaa qaacidada hore loo xaqiijiyay ee ficilka ah: Dobbles (for \((k-1)\) prim) waxaa lagu soo saari karaa riixitaanka badhan:

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

Dib u laabo