Feladat:	2016. évi Nemzetközi Matematika Diákolimpia 12. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Lajkó Kálmán
Füzet:	2016/október, 388 - 389. oldal		PDF  |  MathML
Témakör(ök):	Nemzetközi Matematikai Diákolimpia, Számelrendezések, Oszthatóság
Hivatkozás(ok):	Feladatok: 2016/szeptember: 2016. évi Nemzetközi Matematika Diákolimpia 12. 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.   Lajkó Kálmán megoldása. Keressük meg az ilyen $n\times n$-es négyzeteket! Ha egy négyzetre van megfelelő kitöltés, akkor $3\mid n$, ez nyilvánvaló. Azt se nehéz látni, hogy ha van egy $n\times n$-es négyzetre egy kitöltésünk, akkor minden $\left(kn\right)\times \left(kn\right)$-es négyzetre is, hiszen jó kitöltésű $n\times n$-es négyzetből $k^2$-et egymásra lehet pakolni, ekkor a sorok és oszlopok nyilván eleget tesznek a feltételeknek, és az átlók is, mivel belátható, hogy ha egy átló hossza a $kn$-es négyzetben hárommal osztható, akkor az átlónak az egyes $n$-es négyzetekkel vett metszetei is hárommal osztható hosszúságúak.     Érdemes kis négyzetekre az állítást kipróbálni, az $n=9$ esetre van kitöltés is, így már lehet tudni, hogy a $9\mid n$-es négyzetekre mindig van kitöltés. Ezután megpróbáljuk belátni, hogy ha $n$ nem osztható kilenccel, de hárommal igen, akkor nem lehet kitölteni a négyzetet. Ezt indirekten csináljuk, tegyük fel, hogy ki lehet tölteni egy ilyen $\left(n=3k\right)$-s táblázatot, ahol $k$ nem osztható $3$-mal. Erre a csomó betűre vonatkozó hárommal való oszthatóságot össze lehet adogatni, ki lehet vonni egymásból, az eredményre is igaz lesz hogy a betűk egyharmada I, M és O (ez ilyen egyenletrendszeres ötlet). Ezt úgy kell érteni, hogy ha többször van egy mező I betűje az összegben, akkor annyiszor adódik hozzá az I-k számához, vagy a kivonás miatt lehet hogy negatív sokszor szerepel az összegben, és ekkor ez levonódik az I-k számából. Az összegben tehát mezők betűi szerepelnek, egész sokszor, és az I-k, M-ek és O-k száma azonos.     Vegyük a táblázatunkat, adjuk össze az összes hárommal osztható átlót (vagyis hogy összesen hány I, M, O van bennük összesen), adjuk hozzá a 2.; 5.; 8.; $\text{...}$; $\left(3l+2\right)$-edik oszlopokat, és ebből vonjuk ki az összes az 1., 3., 4., 6. stb. sorokat, vagyis a nem $\left(3l+2\right)$-edik sorokat. Nézzük meg, hogy ebben hány darab I betű van. Az átlókból van $3;6;\text{...};3k;3k-3;\text{...};3$ hosszú, mindkét irányban, ezekben összesen $2\left(1+2+\text{...}k+1+2+\text{...}+\left(k-1\right)\right)=k\left(k+1\right)+\left(k-1\right)k=2k^2$ darab I betű van. Az oszlopokban van $\frac{kn}{3}=k^2$, és ebből még le kell vonni a sorokban lévő I-k számát, ami $2k\cdot \frac{n}{3}=2k^2$. Ezeket összegezve, az I-k száma: $2k^2+k^2-2k^2=k^2$, ami hárommal nem osztható. Viszont ha megnézzük, hogy az egyes mezőket hányszor számoltunk az összegben, akkor azt figyelhetjük meg, hogy a nem $3l+2$ alakú sorokban lévő mezők pont kiesnek, és a visszamaradó mezőket mind háromszor számoltuk meg, a két átlóban és az oszlopokban, ezek a $\left(3x+2;3y+2\right)$ koordinátájú mezők. Ez azt jelenti, hogy az I-k száma az összegben hárommal osztható kell hogy legyen. Ez ellentmondás.