 |
Az A. 856. feladat (2023. május) |
A. 856. Egy kő-papír-olló bajnokságban a versenyzők teljes körmérkőzést játszanak, és bármely két versenyző tíz menetben ütközik meg egymással. Minden versenyzőnek van egy kedvenc stratégiája, egy előre leírt tízes (például KKOPPKOPPO), és minden ellenfél ellen ugyanazt a tíz kezet mutatja (az előre leírt sorrendben). A bajnokság végén kiderült, hogy minden versenyző legyőzte legalább egy menetben mindegyik másikat.
Bizonyítsuk be, hogy legfeljebb \(\displaystyle 1024\) versenyző vett részt a bajnokságban.
Javasolta: Matolcsi Dávid (Budapest)
(7 pont)
A beküldési határidő 2023. június 12-én LEJÁRT.
A megoldás során használni fogjuk a lineáris algebrából ismert vektortér és lineáris függetlenség fogalmát, illetve azt az állítást, hogy egy vektortér nem tartalmazhat a dimenziójánál több lineárisan független vektort.
A kő, papír, olló mutatásokat rendre azonosítjuk a \(\displaystyle 0, 1, 2\) maradékokkal mod \(\displaystyle 3\).
Minden \(\displaystyle A\) játékosra létrehozom a \(\displaystyle p_A(x_1,x_2,\ldots,x_{10})\) polinomot. Ha az \(\displaystyle A\) játékos az \(\displaystyle a_1,a_2, \ldots,a_{10}\) sorozatot mutatja, akkor
\(\displaystyle p_A(x_1,\ldots,x_{10})=\prod_{i=1}^{10} (x_i-a_i-1)\)
Figyeljük meg, hogy \(\displaystyle p_A(a_1,\ldots,a_{10})=(-1)^{10}=1\), ez még hasznunkra lesz később.
viszont tetszőleges másik \(\displaystyle B\) játékos \(\displaystyle b_1, \ldots,b_{10}\) mutatási sorozatára teljesül, hogy \(\displaystyle B\) valamikor megveri \(\displaystyle A\)-t, tehát létezik olyan \(\displaystyle i\), amire \(\displaystyle b_i\equiv a_i+1\) mod \(\displaystyle 3\), azaz
\(\displaystyle p_A(b_1,\ldots,b_n)\equiv 0 \mod 3\)
Mostantól tekintsük a \(\displaystyle p_A\) polinomokat \(\displaystyle \mathbb{F}_3\) (azaz a 3-as maradékok teste) fölött, azaz vegyük az együtthatóiknak azok \(\displaystyle 3\)-as maradékát.
Legyen a játékosok száma \(\displaystyle n\). Tegyük föl, hogy léteznek \(\displaystyle c_1,\ldots,c_n\) együtthatók modulo \(\displaystyle 3\), amikre teljesül, hogy
\(\displaystyle Q=c_1p_{A_1}+c_2p_{A_2}+\ldots+c_np_{A_n}=0,\)
azaz ha ezekkel a súlyokkal összeadjuk a polinomokat, akkor az összegként kapott polinom minden együtthatója \(\displaystyle 0\) lesz modulo \(\displaystyle 3\).
Helyettesítsük be a \(\displaystyle Q\) polinomba az \(\displaystyle A_k\) játékos sorozatát. Ekkor \(\displaystyle c_kp_{A_k}\) értéke \(\displaystyle c_k\) lesz, viszont minden \(\displaystyle j\ne k\)-ra \(\displaystyle p_{A_j}\)-be helyettesítve \(\displaystyle 0\)-t kapunk, így a teljes összeg \(\displaystyle c_k\) lesz. Másrészt feltettük, hogy a \(\displaystyle Q\) polinom minden együtthatója \(\displaystyle 0\) modulo \(\displaystyle 3\), amiből az következik, hogy bármit helyettesítünk be, \(\displaystyle 0\)-t kell adnia mod \(\displaystyle 3\). Ezzel megkaptuk, hogy \(\displaystyle c_k= 0\) minden \(\displaystyle k\)-ra.
Ez azt jelenti, hogy a \(\displaystyle p_A\) polinomok lineárisan függetlenek \(\displaystyle \mathbb{F}_3\) fölött: csak akkor lehet egy súlyozott összegük \(\displaystyle 0\), ha minden súly \(\displaystyle 0\).
Nevezzük \(\displaystyle V\)-nek az \(\displaystyle \mathbb{F}_3\) fölötti \(\displaystyle (x_1, x_2, \ldots , x_n)\) polinomok azon vektorterét, amit az olyan monomok feszítenek ki, amikben minden változó legfeljebb egyszer szerepel. Ilyen monomból \(\displaystyle 2^{10}\) van, így \(\displaystyle V\) dimenziója \(\displaystyle 2^{10}=1024\).
Vegyük észre, hogy egy \(\displaystyle p_A\) polinomban csak ilyen monomok vannak, így minden \(\displaystyle p_A\) polinom a \(\displaystyle V\) vektortérben van. Egy vektortérben nem lehet a dimenziónál több független elem, és tudjuk, hogy a \(\displaystyle p_A\) polinomok lineárisan függetlenek \(\displaystyle \mathbb{F}_3\) fölött, tehát a játékosok száma legfeljebb \(\displaystyle 1024\).
—
Megjegyzés: Ez a bizonyítás Aart Blokhuis 1992-es, On the Sperner Capacity of the Cyclic Triangle című cikkéből származik.
Statisztika:
0 dolgozat érkezett.
A KöMaL 2023. májusi matematika feladatai