Problem C. 1881. (December 2025)

C. 1881. Given an \(\displaystyle n\times n\) chessboard, we want to cover it without overlaps using L-shaped pieces consisting of 3 squares, in such a way that at most one square remains uncovered. Prove that this is possible for any positive integer \(\displaystyle n\neq 3\). (All the sides of the L-shape should follow the grid lines.)

Proposed by Mátyás Czett, Zalaegerszeg

(5 pont)

Deadline expired on January 12, 2026.

Sorry, the solution is available only in Hungarian. Google translation

Megoldás. Először is készítsünk listát arról, hogy milyen téglalapokat tudunk maradéktalanul lefedni L alakú elemekkel viszonylag könnyedén.

• Két elem megfelelő összeillesztésével egy \(\displaystyle 2\times3\)-as téglalap könnyen lefedhető.
• 2 db \(\displaystyle 2\times3\)-as lefedett téglalap felhasználásával készíthető \(\displaystyle 2\times6\)-os, 3 db \(\displaystyle 3\times2\)-es lefedett téglalap egymásra helyezésével pedig \(\displaystyle 3\times6\)-os lefedett téglalap.
• Az előző két téglalapot jól használhatjuk tetszőleges \(\displaystyle 6\times n\)-es téglalap fedésére, ha \(\displaystyle n\geq 2\). Ehhez páros \(\displaystyle n\) esetén \(\displaystyle \frac{n}{2}\) db \(\displaystyle 2\times6\)-os, páratlan \(\displaystyle n\) esetén egy \(\displaystyle 3\times6\)-ost és megfelelő számú (\(\displaystyle \frac{n-3}{2}\) db) \(\displaystyle 2\times 6\)-es téglalapot kell egymás mellé helyeznünk.

Ezután belátjuk, hogy az \(\displaystyle n\times n\)-es négyzet megfelelő fedése \(\displaystyle n\leq 9\) és \(\displaystyle n\neq 3\) esetén megtehető. Az \(\displaystyle n=1\) esetben sikerrel jártunk anélkül, hogy letettünk volna elemet, az \(\displaystyle n=2, n=4, n=5\) esetet az ábra első sora mutatja. A \(\displaystyle 6\times 6\)-os sakktábla lefedését már láttuk korábban a téglalapok vizsgálatánál, a \(\displaystyle 7\times7\)-es, \(\displaystyle 8 \times 8\)-as és \(\displaystyle 9 \times 9\)-es eset pedig a második sorban látható. Az ábrán a téglalapok \(\displaystyle 2\times 3\)-as táblákat jelölnek, melyek maradéktalan fedését korábban megmutattuk.

A bizonyítás folytatásához szükség van a következő segédállításra:

Állítás: Ha az \(\displaystyle n\times n\)-es négyzet megfelelően lefedhető, akkor az \(\displaystyle (n+6) \times (n+6)\)-os négyzet is lefedhető megfelelően.

Bizonyítás: Az \(\displaystyle (n+6) \times (n+6)\)-os négyzet felbontható négy téglalapra a lenti ábrán látható módon, 1 db \(\displaystyle n\times n\)-esre, 2 db \(\displaystyle n\times 6\)-osra és 1 db \(\displaystyle 6\times 6\)-osra. Mivel korábban láttuk, hogy a négy téglalap közül az \(\displaystyle n\times 6\)-osok és a \(\displaystyle 6\times 6\)-os teljesen lefedhetőek L alakú elemekkel, az \(\displaystyle n\times n\)-es pedig az állítás feltevése szerint legfeljebb egy négyzet kihagyásával lefedhető, ezért igaz az állítás. \(\displaystyle \blacksquare\)

A segédállítást felhasználva a feladat állítása teljes indukció segítségével könnyen igazolható. Ha ugyanis egy \(\displaystyle k\) oldalhosszúságú sakktáblát \(\displaystyle (k>9)\) kell lefednünk, először számoljuk ki \(\displaystyle k\) hatos maradékát. Ha a \(\displaystyle k\) hatos maradéka \(\displaystyle 0\), akkor induljunk ki egy \(\displaystyle 6\times 6\)-os tábla lefedéséből, majd a segédállításban látott módon bővítsük ezt \(\displaystyle 12\times 12\)-es lefedéssé, majd \(\displaystyle 18\times 18\)-as lefedéssé, stb. Az eljárást kellő számban megismételgetve megkapjuk egy \(\displaystyle k\times k\)-as tábla megfelelő lefedését.

Más hatos maradékok esetén hasonlóan járhatunk el: ha \(\displaystyle k\) hatos maradék 1, a \(\displaystyle 7\times 7\)-es tábla lefedéséből induljunk ki, és azt bővítgessük, ha a hatos maradék 2, akkor \(\displaystyle 2\times 2\)-esből, ha a maradék 3, akkor \(\displaystyle 9\times9\)-esből, ha a maradék 4, akkor \(\displaystyle 4\times 4\)-esből, ha pedig a maradék 5, akkor \(\displaystyle 5\times 5\)-ösből. A segédállítás felhasználásával így igazoltuk a feladat állítását.

Megjegyzés: Bár a feladat szövege nem kéri, a probléma teljes vizsgálatához hozzátartozik annak bizonyítása, hogy \(\displaystyle n=3\) esetén a lefedés nem megvalósítható. \(\displaystyle 3\times3\)-as tábla esetén teljes fedést kellene létrehoznunk, hisz az L betűkkel fedett mezők száma mindenképpen a 3 többszöröse. Hogy teljes fedés miért nem lehetséges, indirekt igazolható, például esetszétválasztással a jobb alsó sarkot fedő elem elhelyezkedése szerint.

De gondolkodhatunk így is: színezzük a \(\displaystyle 3\times 3\)-as sakktáblát sakktáblaszerűen, a bal felső elem legyen fehér. Mivel így 5 fehér és 4 fekete mező keletkezik, ezért az L betűk közül kettőnek kell 2 fehér mezőt fedni, egynek pedig egyet (3 és 0 fehér mezőt nem tud fedni L betű). Viszont egy L betű csak akkor fedhet 2 fehér mezőt, ha letakarja a középső mezőt is. Ezek szerint megfelelő fedés esetén a középső mezőt két elem is takarná, ami ellentmondás.

Statistics:

34 students sent a solution.
5 points:	Albert Luca Liliána, Bao Nguyen Gia, Budai Máté, Hetyei Dániel, Kámán-Gausz Péter, Mateas Isabelle, Nelissen Sámuel Zalán, Németh Ábel, Viczián Adél.
4 points:	Aaishipragya Kahaly, Bán Kincső Panni, Hirmann Dorottya, Móricz Zsombor, Szedmák Szabrina, Válek Péter.
3 points:	7 students.
2 points:	5 students.
1 point:	3 students.
0 point:	1 student.
Unfair, not evaluated:	2 solutionss.

Problems in Mathematics of KöMaL, December 2025