Акыркы үй-бүлөлүк оюн кечесинде балдар кубаныч менен Dobble оюнун (Гарри Поттер басылышы) чыгарышты. Беш раундда утулуп калгандан кийин (менин картам оюн картасына дал келбей калгандыктан), ар бир оюнчу ар бир раундда дал келгенин таба аларын билип таң калдым. Бирок, менин ишенбестигим жоголгон раунддардын көбөйүшү менен гана коштолду – балдар жөн гана тезирээк болушту.
Математикалык көз караш менен оюнду жакшыраак карап чыгуу үчүн жетиштүү себеп. Биринчи оюндун принциби: Dobble – бул ар бири сегиз түрдүү символду көрсөткөн \(55\) тегерек карталары бар жөнөкөй карта оюну. Бардык карталар өз кезегинде бөлүштүрүлүп, үстөлдүн ортосунда акыркы карта гана калат. Эми бардык оюнчулар бир эле учурда картадагы символдорду учурдагы жогорку картасындагы символдор менен салыштырышы керек. Эгерде оюнчу эки картада тең бирдей символду тапса, ал символду эң тез атаган болуп, өз картасын стекке коё алат. Бардык карталарын биринчи таштаган оюнчу жеңет.
Кандайча \(55\) карта бар, алар 2 картада так бир жалпы символду камтыгандай курулган? Мындай символдордун минималдуу саны канча болушу керек? Мындай карталардын максималдуу саны канча?
Биринчиден, биз бул карталарды төмөнкү логикалык кадамдарды колдонуу менен курабыз (кийинки бардык түзүлгөн карталар өсүү тартибинде иреттелген касиетке ээ): Биринчи картада 8 түрдүү символ болушу керек, б.а.:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Төмөнкү карталарды биринчи карта менен бирдей жалпы белгиге ээ болушу үчүн кантип курабыз?:
$$\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\) менен баштап өсүү тартибинде толтурасыз). Бул майда-чүйдө окуя кызыксыз, бирок бизди символдордун минималдуу саны (жана карталардын максималдуу саны) болгон топтом кызыктырууда. Эми биз ар бир картанын экинчи белгиси \( 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} \) (эң сол жактагы карта) башка карталардын ар биринин экинчи символуна дал келиши мүмкүн (антпесе эки окшош белги болот) ).
Биз бул 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\) жаңы символдор абдан керек деген тыянакка келебиз (эч бир картада кайталанма символ болушу мүмкүн эмес жана ар бир ыйгарылган символ эки жолу көрүнбөй калышы мүмкүн, анткени \(1\) эки эселенген):
$$\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}$$
Эми биз биринчи эки картаны элестетебиз (башталгыч символдордон баштап \ \(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}$$
Экинчи туташтыруучу сызык ( \(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 \)
- Иш 1а: \( 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\)
- \(y_1 = 1\) жана \(y_2 = 1\) :
- Иш 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 \)
- \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) жана \(y_2 = 1\) үчүн бизде:
- Иш 1а: \( 0 < x_2 < k \)
- 2-иш: \( 0 < x_1 < k \)
- Иш 2а: \( 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)\)
- \(y_1 = 1\) жана \(y_2 = 1\) :
- Иш 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\).
Бул жерде бир гана чечим бар \( (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\).
- \(y_1 = 1\) жана \(y_2 = 1\) :
- Иш 2а: \( 0 < x_2 < k \)
- 3. Case: \( 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\).
- \(y_1 = 1\) жана \(y_2 = 1\) :
- Иши 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\).
- \(y_1 = 1\) жана \(y_2 = 1\) :
- Иш 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\)
- Иш 3a: \( x_2 \geq k \)
Ошондой эле бул жерден же бул жерден доббл жана математика темасы боюнча кызыктуу маалымат таба аласыз . Төмөнкү скриптте мурда далилденген формуланы иш жүзүндө көрө аласыз: Добблдерди ( \((k-1)\) үчүн) баскычты басуу менен түзсө болот.:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.