En la lasta familia vespero, la ludo Dobble (en la Harry Potter Edition) estis entuziasme alportita al la tablo fare de la infanoj. Post la 5-a perdita raŭndo (sen videbla trafo de mia karto per la ludkarto) oni diris al mi, je mia miro, ke ĉiu ludanto ĉiam povas trovi trafon en ĉiu raŭndo. Sed mia nekredemo estis agnoskita nur per pluaj perditaj rondiroj - la infanoj simple estis pli rapidaj.
Sufiĉa kialo por pli detale rigardi la ludon el matematika vidpunkto. Unue la ludprincipo: Dobble estas simpla kartludo kun \(55\) rondaj kartoj, ĉiu montrante ok malsamajn simbolojn. Ĉiuj kartoj estas distribuitaj laŭvice, lasante nur la lastan karton en la mezo de la tablo. Nun ĉiuj ludantoj devas samtempe kompari la simbolojn sur la karto kun la simboloj sur sia nuna supra karto. Se ludanto trovis la saman simbolon sur ambaŭ kartoj, li povas meti sian karton sur la stakon estante la plej rapida por nomi la simbolon. La ludanto kiu unue forĵetas ĉiujn siajn kartojn venkas.
Kiel povas esti, ke ekzistas \(55\) tiaj kartoj, kiuj estis konstruitaj tiel, ke iuj ajn 2 kartoj havas ĝuste unu simbolon komune? Kio estas la minimuma nombro de tiaj simboloj, kiujn oni devas uzi? Kio estas la maksimuma nombro de tiaj kartoj?
Unue, ni konstruas ĉi tiujn kartojn uzante la sekvajn logikajn paŝojn (ĉiuj poste konstruitaj kartoj havas la econ, ke ili estas ordigitaj en kreskanta ordo): La unua karto devas havi 8 malsamajn simbolojn, t.e. legas.:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
Ni nun konstruas la sekvajn kartojn tiel, ke ili havas ĝuste unu simbolon komunan kun la unua karto:
$$\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)$$
Iu ajn nombro da tiaj kartoj jam povas esti konstruita ĉi tie (vi simple plenigu la lokojn en kreskanta ordo, komencante per \(9\) ). Ĉi tiu bagatela kazo estas tamen neinteresa, ĉar ni interesiĝas pri aro kun minimuma nombro da simboloj (kaj maksimuma nombro da kartoj). Ni nun konsideru la duan simbolon \( x_{l.2} \) de ĉiu karto, por kiu evidente devas apliki la jenon: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . Ni do nepre enkondukis \( k \) novajn simbolojn. Sed nun \( k \leq 8-1 = 7 \) , ĉar neniu el la \( 7 \) simboloj \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (de la plej maldekstra karto) povas egali la duan simbolon de ĉiu el la aliaj kartoj (alie estus du identaj simboloj ).
Ni trovis maksimumon de ĉi tiuj 7 novaj kartoj:
$$\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)$$
Kun la sama argumento ni nun konstruas la sekvajn \(7\) mapojn (la unua el ĉi tiuj mapoj devas kolizii kun nia komenca mapo, kaj ne kun \(1\) , alie ĝi estus kun la \(7\) antaŭe. trovitaj mapoj):
$$\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)$$
Ĉi tiu argumento ankaŭ povas esti daŭrigita por la sekvaj \(7\) kartoj; Entute \(8-2 = 6\) pliajn fojojn. La lastaj \(7\) kartoj estas laŭe:
$$\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)$$
Se vi aldonus alian karton $$\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)$$ malsukcesos ĉar ĉi tiu karto ne kunhavas simbolon kun la komenca karto. Ni konstruis maksimumon de \(1 + 8 \cdot 7 = 57\) mapoj. Nia celo nun estas konstrui almenaŭ tiom da.
Por fari tion, ni rigardas la unuajn 7 novajn kartojn trovitajn kaj venas al la konkludo, ke ni nepre bezonas \(7 \cdot 7\) novajn simbolojn ĉi tie (neniu karto povas havi simbolon dufoje kaj ĉiu simbolo asignenda ne devas aperi. dufoje, ĉar kiu \(1\) jam estas duobla):
$$\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)$$
Do ni bezonas minimumajn \(8 + (7 \cdot 7) = 57\) simbolojn (do tiom da simboloj kiom kartoj!). Ni nun provas sukcesi kun ĉi tiu nombro kaj trovi konstruregulon por ĉiuj aliaj elementoj. Por fari tion, ni konstruas iomete pli malgrandan dobleton kiu havas nur \(3\) simbolojn per karto kaj ricevas ĝin kiel la komenca karto.
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
kaj la aliaj kartoj
$$\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)$$
kun entute \(1 + 3 \cdot 2 = 7\) kartoj kaj \( 3 + (2 \cdot 2) = 7\) simboloj. Kun iom da provo kaj eraro (kaj uzante la simbolojn jam asignitajn) vi ricevas la jenan dobble:
$$\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)$$
Ĉu ankaŭ tion oni povas trovi sisteme? Por fari tion, ni enigas la nove asignitajn simbolojn \(4, 5, 6, 7\) en kvadrata matrico:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Nun ni imagu por la unuaj du kartoj (komencante per la komencaj simboloj \ \(4\) kaj \(5\) ) vertikalajn kunligajn liniojn al la malsuperaj simboloj \(6\) kaj \(7\):
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Ĉar ĉi tiuj linioj ne intersekcas, ni ricevas (tramante la simbolojn sur la kunligaj linioj linio post linio) la plej proksimajn validajn kartojn.:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Fine, ni imagas kunligajn liniojn kun malsama deklivo (en ĉi tiu kazo kun la deklivo \(1\) ):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
La dua liglinio (inter \(5\) kaj \(6\) ) forlasas la matricon ĉe la dekstra rando kaj reeniras ĉe la maldekstra rando. Lerte elektante la deklivon, ni certigas unuflanke, ke la kunligaj linioj ne intersekcas unu kun la alia, sed ankaŭ ke la antaŭaj (vertikalaj) kunligaj linioj ne intersekcas. Ĉi tiu dezajna ideo finfine kondukas al la sekva dezajna formulo:
Doble kun \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) havas \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) kartoj kaj simboloj. Por la mapo \(K_x\) kun \(x \in \mathbb{N}\) kaj \(0 \leq x \leq (k-1) \cdot k\) validas:
$$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.$$
Estas \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) pecoj de ĉi tiuj kartoj. Nun restas nur montri:
$$ \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-a kazo: \( x_1 = 0 \)
- Kazo 1a: \( 0 < x_2 < k \)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
\(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\) . - Por \(y_1 \neq 1\) kaj \(y_2 = 1\) havas:
\(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\) - Por \(y_1 = 1\) kaj \(y_2 \neq 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 \neq 1\) estas:
\(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\)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
- Kazo 1b: \( x_2 \geq k \)
- Por \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kaj \(y_2 = 1\) ni havas:
\(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\) - Por \(y_1 \neq \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kaj \(y_2 = 1\) estas:
\(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\) - Por \(y_2 \neq 1\) estas:
\(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 \)
- Por \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) kaj \(y_2 = 1\) ni havas:
- Kazo 1a: \( 0 < x_2 < k \)
- 2a kazo: \( 0 < x_1 < k \)
- Kazo 2a: \( 0 < x_2 < k \)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 = 1\) havas:
\(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\) - Por \(y_1 = 1\) kaj \(y_2 \neq 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 \neq 1\) estas:
\(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)\)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
- Kazo 2b: \( x_2 \geq k \)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
\(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\) - Por \(y_1 = 1\) kaj \(y_2 \neq 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 = 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 \neq 1\) estas:
\((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) \)
Por \(y_2 = x_1+1\) kun \( 2 \leq y_2 \leq k\) estas
\(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)\) kun \( 2 \leq y_1 \leq k\).
Estas nur unu solvo ĉi tie \( (y_1, y_2) \).
Ĉar ni elektas \(y^*_2=y_2-1\) kiel valoro, estas \(y^*_1 = y_1-(k-1) < 2\).
Krome, por \(y^*_2*=y_2+1\) tiam \(y^*_1 = y_1+(k-1) > k\).
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
- Kazo 2a: \( 0 < x_2 < k \)
- 3. Kazo: \( x_1 \geq k \)
- Kazo 3a: \( x_2 \geq k \)
- Kazo 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\)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
\(f(x_1, y_1) = f(x_1, 1) = m_1\)
\(f(x_2, y_2) = f(x_2, 1) = m_2 = m_1\) - Por \(y_1 = 1\) kaj \(y_2 \neq 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 = 1\) havas:
Vidu \(y_1 = 1\) kaj \(y_2 \neq 1\) . - Por \(y_1 \neq 1\) kaj \(y_2 \neq 1\) estas:
\(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)\)
Tiam \(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)\)
Por \(y_1 \neq y_2\) estas \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Por \(y_1 = y_2\) estas \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) kaj
\(\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\) en kontraŭdiro al \(m_1 = m_2\).
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
- Kazo 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\)
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
\(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\) - Por \(y_1 = 1\) kaj \(y_2 \neq 1\) havas:
\(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\) - Por \(y_1 \neq 1\) kaj \(y_2 = 1\) havas:
Vidu \(y_1 = 1\) kaj \(y_2 \neq 1\) . - Por \(y_1 \neq 1\) kaj \(y_2 \neq 1\) estas:
\(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)\)
Tiam \(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)\)
Por \(y_1 \neq y_2\) estas \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Por \(y_1 = y_2\) estas \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) kaj
\(\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}\)
Nu tie por \(2 \leq y \leq k\) ĉiam a \(l \in \mathbb{N}_0\), tiel ke
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Pruvo: tie \((k-1)\) estas primo, estas (pro la lemo de Bézout)
\((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
solvebla, ĉar \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Splitoj \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
Tiam ĉi tio estas la sola solvo \(l_1\), ĉar por unu
\(l_2 = l_1 + (m_2-m_1)\) estas \( y_2 = y_1 + (k-1) > k\).
- Por \(y_1 = 1\) kaj \(y_2 = 1\) havas:
- Kazo 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\)
- Kazo 3a: \( x_2 \geq k \)
Vi ankaŭ povas trovi interesajn fonajn informojn pri la temo de dobble kaj matematiko ĉi tie aŭ ĉi tie . En la sekva skripto vi povas vidi la antaŭe pruvitan formulon en ago: Dobbles (por \((k-1)\) prim) povas esti generitaj per premo de butono:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.