Feladat:	2018. évi Nemzetközi Matematika Diákolimpia 21. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Egri Máté
Füzet:	2018/november, 451. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Többszemélyes véges játékok
Hivatkozás(ok):	Feladatok: 2018/szeptember: 2018. évi Nemzetközi Matematika Diákolimpia 21. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.   Egri Máté megoldása. Azt bizonyítjuk, hogy $K=100$. Két hely távolsága akkor $\sqrt[]{5}$, ha ,,lólépésre'' vannak egymástól, azaz kettőt az egyik irányba, egyet pedig arra merőlegesen lépünk. Tehát ha a helyeket ,,sakktáblaszerűen'' kiszínezzük, akkor bármely két hely, aminek távolsága $\sqrt[]{5}$, különböző színű. Ekkor ha Anna azt a stratégiát követi, hogy csak a fekete helyekre rak (amikből 200 van), akkor legalább azok felére tud rakni, azaz 100 helyre. Tehát $K\ge 100$. A $20\times 20$-as táblát feloszthatjuk 25 db $4\times 4$-es táblára. Bebizonyítjuk, hogy egy $4\times 4$-es táblán Balázs garantálni tudja, hogy Anna csak 4 helyre tudjon tenni. Ha így betűzzük meg a $4\times 4$-es táblát és Balázs mindig Anna lépésével a tábla középpontjára tükrös helyre rak, akkor Anna már nem rakhat többször ugyanolyan betűre, így valóban legfeljebb négyszer rakhat. 25 db $4\times 4$-es tábla van, tehát $K\le 100$. Mivel $K\ge 100$ és $K\le 100$, ezért $K=100$. ${\displaystyle \begin{array}{|cccc|}\hline \hfill {\displaystyle \text{A}}\hfill & \hfill {\displaystyle \text{ B}}\hfill & \hfill {\displaystyle \text{ C}}\hfill & \hfill {\displaystyle \text{ D }}\hfill \\ \hfill {\displaystyle \text{C}}\hfill & \hfill {\displaystyle \text{ D}}\hfill & \hfill {\displaystyle \text{ A}}\hfill & \hfill {\displaystyle \text{ B }}\hfill \\ \hfill {\displaystyle \text{B}}\hfill & \hfill {\displaystyle \text{ A}}\hfill & \hfill {\displaystyle \text{ D}}\hfill & \hfill {\displaystyle \text{ C }}\hfill \\ \hfill {\displaystyle \text{D}}\hfill & \hfill {\displaystyle \text{ C}}\hfill & \hfill {\displaystyle \text{ B}}\hfill & \hfill {\displaystyle \text{ A }}\hfill \\ \hline\end{array}}$