Վերջին ընտանեկան երեկոյին « Դոբլ » խաղը (Հարրի Փոթերի հրատարակությունում) երեխաների կողմից խանդավառությամբ սեղանի շուրջ բերվեց: 5-րդ պարտված ռաունդից հետո (առանց խաղաքարտի իմ քարտի տեսանելի հարվածի) ինձ ասացին, ի զարմանս ինձ, որ յուրաքանչյուր խաղացող միշտ կարող է հարված գտնել յուրաքանչյուր ռաունդում: Բայց իմ անհավատությունը ճանաչվեց միայն հետագա կորցրած պտույտներով. երեխաները պարզապես ավելի արագ էին:
Բավական պատճառ՝ խաղը մաթեմատիկական տեսանկյունից ավելի մոտիկից նայելու համար: Նախ խաղի սկզբունքը. 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} \) որի համար ակնհայտորեն պետք է կիրառվի հետևյալը. \( 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\) ) մատրիցը թողնում է աջ եզրին և նորից մտնում ձախ եզրում: Հմտորեն ընտրելով թեքությունը՝ մենք մի կողմից ապահովում ենք, որ միացնող գծերը միմյանց հետ չհատվեն, բայց նաև նախորդ (ուղղահայաց) միացնող գծերը չհատվեն։ Դիզայնի այս գաղափարը, ի վերջո, հանգեցնում է դիզայնի հետևյալ բանաձևին:
Dobble-ը \(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\) ունենք.
- Գործ 1բ: \( 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\) ունենք.
- Գործ 2բ: \( 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. Գործ: \( x_1 \geq k \)
- Գործ 3ա: \( x_2 \geq k \)
- Գործ 3ա: \(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\) ունենք.
- Գործ 3ա'': \(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\) ունենք.
- Գործ 3ա: \(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\)
- Գործ 3ա: \( x_2 \geq k \)
Դոբլի և մաթեմատիկայի թեմայի վերաբերյալ հետաքրքիր ֆոնային տեղեկություններ կարող եք գտնել այստեղ կամ այստեղ : Հետևյալ սցենարում դուք կարող եք տեսնել նախկինում ապացուցված բանաձևը գործողության մեջ. Dobbles ( \((k-1)\) prim-ի համար) կարող է ստեղծվել կոճակի սեղմումով::
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.