Az utolsó családi esten a Dobble játékot (a Harry Potter kiadásban) hozták le a gyerekek lelkesen asztalhoz. Az 5. elvesztett kör után (amikor a kártyám nem volt látható a játékkártyával) meglepetésemre azt mondták nekem, hogy minden játékos minden körben találhat egy találatot. De hitetlenkedésemet csak újabb vesztett körökkel nyugtázták – a gyerekek egyszerűen gyorsabbak voltak.
Elég ok arra, hogy közelebbről megvizsgáljuk a játékot matematikai szempontból. Először is a játék elve: A Dobble egy egyszerű kártyajáték \(55\) kerek kártyákkal, amelyek mindegyike nyolc különböző szimbólumot mutat. Az összes lapot sorra osztják, csak az utolsó kártya marad az asztal közepén. Most minden játékosnak egyszerre kell összehasonlítania a kártyán lévő szimbólumokat az aktuális felső kártyáján lévő szimbólumokkal. Ha egy játékos mindkét kártyán ugyanazt a szimbólumot találta, a kártyáját a pakliba helyezheti úgy, hogy ő a leggyorsabb a szimbólum megnevezésére. Az a játékos nyer, aki először eldobja az összes kártyáját.
Hogyan lehet, hogy vannak \(55\) olyan kártyák, amelyek úgy lettek megszerkesztve, hogy bármelyik 2 kártyán pontosan egy közös szimbólum van? Mennyi az ilyen szimbólumok minimális száma, amelyet kell használni? Mennyi az ilyen kártyák maximális száma?
Először a következő logikai lépésekkel készítjük el ezeket a kártyákat (minden később megszerkesztett kártya rendelkezik azzal a tulajdonsággal, hogy növekvő sorrendben vannak rendezve): Az első kártyának 8 különböző szimbólummal kell rendelkeznie, azaz olvasni.:
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \end{array}\right)$$
A következő kártyákat most úgy készítjük el, hogy pontosan egy közös szimbólumuk legyen az első lappal:
$$\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)$$
Itt már tetszőleges számú ilyen kártya összeállítható (egyszerűen töltse ki a helyeket növekvő sorrendben, \(9\) kezdve). Ez a triviális eset azonban érdektelen, mivel minket egy minimális számú szimbólum (és maximális számú kártya) tartalmazó halmaz érdekel. Most figyelembe vesszük az egyes kártyák második szimbólumát \( x_{l.2} \) , amelyre nyilvánvalóan a következőket kell alkalmazni: \( x_{1.2} \neq x_{2.2} \neq x_{3.2} \neq \ldots \neq x_{k.2} \) . Ezért szükségszerűen bevezettünk \( k \) új szimbólumokat. De most \( k \leq 8-1 = 7 \) , mivel a \( 7 \) szimbólumok egyike sem \( x_{1.2},\, x_{1.3},\, x_{1.4},\, x_{1.5},\, x_{1.6},\, x_{1.7},\, x_{1.8} \) (a bal szélső kártya) megegyezhet a többi kártya második szimbólumával (különben két azonos szimbólum lenne ).
Legfeljebb 7 új kártyát találtunk:
$$\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)$$
Ugyanezzel az érvvel most megszerkesztjük a következő \(7\) térképeket (ezen térképek közül az elsőnek ütköznie kell a kezdőtérképünkkel, és nem a \(1\) -vel, különben az előző \(7\) talált térképeket):
$$\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)$$
Ez az argumentum a következő \(7\) kártyákra is folytatható; Összesen \(8-2 = 6\) alkalommal. Az utolsó \(7\) kártyák ennek megfelelően:
$$\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)$$
Ha hozzáadna egy másik kártyát $$\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)$$ sikertelen lesz, mert ez a kártya nem osztozik szimbólumon a kezdőkártyával. Maximum \(1 + 8 \cdot 7 = 57\) térképet szerkesztettünk. Most az a célunk, hogy legalább ennyit megépítsünk.
Ehhez megnézzük az első 7 talált új kártyát, és arra a következtetésre jutunk, hogy itt feltétlenül szükségünk van \(7 \cdot 7\) új szimbólumokra (egy kártyának sem lehet kétszer szimbóluma, és a hozzárendelendő szimbólumok sem jelenhetnek meg kétszer, mivel ami \(1\) már duplája):
$$\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)$$
Tehát minimális \(8 + (7 \cdot 7) = 57\) szimbólumra van szükségünk (tehát annyi szimbólum, ahány kártya!). Most ezzel a számmal próbálunk boldogulni, és az összes többi elemhez konstrukciós szabályt találni. Ehhez készítünk egy kicsivel kisebb dobot, amelyben csak \(3\) szimbólum van kártyánként, és ezt kapjuk kezdőkártyaként.
$$\left(\begin{array}{c} 1 \\ 2 \\ 3 \end{array}\right)$$
és a többi kártya
$$\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)$$
összesen \(1 + 3 \cdot 2 = 7\) kártyával és \( 3 + (2 \cdot 2) = 7\) szimbólummal. Egy kis próbálkozással és hibával (és a már hozzárendelt szimbólumok használatával) a következő dobást kapod:
$$\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)$$
Ezt is meg lehet találni szisztematikusan? Ehhez beírjuk az újonnan hozzárendelt szimbólumokat \(4, 5, 6, 7\) egy négyzetmátrixba:
$$\begin{array}{ccc} 4 & & 5 \\ & & \\ 6 & & 7\end{array}$$
Most képzeljük el, hogy az első két kártya (a \ \(4\) és \(5\) kezdőszimbólumokkal kezdődően) függőleges összekötő vonalak az alsó \(6\) és \(7\) szimbólumokhoz.:
$$\begin{array}{ccc} 4 & & 5 \\ \vdots & & \vdots \\ 6 & & 7\end{array}$$
Mivel ezek a vonalak nem metszik egymást, így megkapjuk (az összekötő vonalakon lévő szimbólumok soronkénti ábrázolásával) a legközelebbi érvényes kártyákat.:
$$\left(\begin{array}{c} 2 \\ 4 \\ 6 \end{array}\right), \left(\begin{array}{c} 2 \\ 5 \\ 7 \end{array}\right)$$
Végül képzeljük el, hogy más meredekségű vonalakat kapcsolunk össze (jelen esetben a \(1\) meredekséggel):
$$\begin{array}{ccccc} & 4 & & 5 & \\ \ddots & & \ddots & & \ddots \\ & 6 & & 7 &\end{array}$$
A második összekötő vonal ( \(5\) és \(6\) között) a mátrixot a jobb szélen hagyja el, és a bal szélen lép vissza. A lejtő ügyes megválasztásával egyrészt biztosítjuk, hogy az összekötő vonalak ne metsszék egymást, hanem azt is, hogy a korábbi (függőleges) összekötő vonalak ne metsszék egymást. Ez a tervezési ötlet végül a következő tervezési képlethez vezet:
A \(k \in \mathbb{N} \, | \, (k-1) \text{ prim} \) \(1+(k \cdot (k-1)) = k^2-k+1 = k + (k-1)(k-1)\) kártyák és szimbólumok. A térképre a \(K_x\) \(x \in \mathbb{N}\) és \(0 \leq x \leq (k-1) \cdot k\) vonatkozik:
$$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.$$
Ezeknek a kártyáknak \((k-1)\cdot k + 1 = k + (k-1)(k-1)\) darabja van. Most már csak megmutatni kell:
$$ \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. eset: \( x_1 = 0 \)
- 1a. eset: \( 0 < x_2 < k \)
- \(y_1 = 1 \(y_1 = 1\) és \(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\) és \(y_2 = 1\) a következőt használjuk:
\(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\) és \(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 \(y_1 \neq 1\) és \(y_2 \neq 1\) esetén a következő:
\(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_1 = 1\) és \(y_2 = 1\) :
- Eset 1b: \( x_2 \geq k \)
- A \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) és \(y_2 = 1\) esetén a következőt kapjuk:
\(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\) és \(y_2 = 1\) esetén:
\(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\) a következő:
\(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 \)
- A \(y_1 = \left\lfloor \frac{x_2-1}{k-1} \right\rfloor + 1\) és \(y_2 = 1\) esetén a következőt kapjuk:
- 1a. eset: \( 0 < x_2 < k \)
- 2. eset: \( 0 < x_1 < k \)
- Eset 2a: \( 0 < x_2 < k \)
- \(y_1 = 1 \(y_1 = 1\) és \(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\) és \(y_2 = 1\) a következőt használjuk:
\(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\) és \(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 \(y_1 \neq 1\) és \(y_2 \neq 1\) esetén a következő:
\(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_1 = 1\) és \(y_2 = 1\) :
- 2b eset: \( x_2 \geq k \)
- \(y_1 = 1 \(y_1 = 1\) és \(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\) és \(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\) és \(y_2 = 1\) a következőt használjuk:
\(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\) - Mert \(y_1 \neq 1\) és \(y_2 \neq 1\) van:
\((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) \)
Mert \(y_2 = x_1+1\) val vel \( 2 \leq y_2 \leq k\) van
\(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)\) val vel \( 2 \leq y_1 \leq k\).
Itt egyetlen megoldás létezik \( (y_1, y_2) \).
Mert mi választunk \(y^*_2=y_2-1\) mint érték, az \(y^*_1 = y_1-(k-1) < 2\).
Ezen kívül azért \(y^*_2*=y_2+1\) azután \(y^*_1 = y_1+(k-1) > k\).
- \(y_1 = 1 \(y_1 = 1\) és \(y_2 = 1\) :
- Eset 2a: \( 0 < x_2 < k \)
- 3. Tok: \( x_1 \geq k \)
- 3a. eset: \( x_2 \geq k \)
- 3a' eset: \(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_1 = 1\) és \(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\) és \(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\) és \(y_2 = 1\) a következőt használjuk:
Lásd \(y_1 = 1\) és \(y_2 \neq 1\) . - Mert \(y_1 \neq 1\) és \(y_2 \neq 1\) van:
\(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)\)
Akkor \(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)\)
Mert \(y_1 \neq y_2\) van \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Mert \(y_1 = y_2\) van \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) és
\(\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\) ellentétben \(m_1 = m_2\).
- \(y_1 = 1 \(y_1 = 1\) és \(y_2 = 1\) :
- Eset 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_1 = 1\) és \(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\) és \(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\) és \(y_2 = 1\) a következőt használjuk:
Lásd \(y_1 = 1\) és \(y_2 \neq 1\) . - Mert \(y_1 \neq 1\) és \(y_2 \neq 1\) van:
\(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)\)
Akkor \(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)\)
Mert \(y_1 \neq y_2\) van \(L_1-L_2 \leq (k-2 - 0) = k-2 < (k-1)(y_2-y_1)\).
Mert \(y_1 = y_2\) van \(L_1 - L_2 = 0 \Leftrightarrow L_1 = L_2\) és
\(\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}\)
Hát oda \(2 \leq y \leq k\) mindig a \(l \in \mathbb{N}_0\), szóval azt
\(m_2 - m_1 \mid (k-1)\cdot l + (3-k)(m_2 - m_1) + (x_1 - x_2)\).
Bizonyíték: van \((k-1)\) prím, van (Bézout lemmája miatt)
\((k-1)\cdot l \equiv -\left( (3-k)(m_2-m_1) + (x_1-x_2) \right) \, \mod (m_2-m_1)\)
megoldható, mert \(\text{ggT}\left((k-1),(m_2-m_1)\right) = 1\) Hasít \(-\left( (3-k)(m_2-m_1) + (x_1-x_2) \right)\).
Akkor ez az egyetlen megoldás \(l_1\), mert egy
\(l_2 = l_1 + (m_2-m_1)\) van \( y_2 = y_1 + (k-1) > k\).
- \(y_1 = 1 \(y_1 = 1\) és \(y_2 = 1\) :
- 3a' eset: \(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. eset: \( x_2 \geq k \)
A dobble és a matematika témakörében is érdekes háttérinformációkat találhat itt vagy itt . A következő szkriptben a korábban bevált képlet látható működés közben: Dobbles (a \((k-1)\) prim-hez) egy gombnyomással generálható:
See the Pen DOBBLE CREATOR by David Vielhuber (@vielhuber) on CodePen.