Problem B. 5161. (March 2021)

B. 5161. \(\displaystyle 800\) L-tetrominoes are laid on a \(\displaystyle 100\times 100\) chesssboard. Prove that it is possible to place another L-tetromino on the board. The tetrominoes do not overlap, and each of them covers exactly \(\displaystyle 4\) fields of the chessboard. An L-tetromino is defined as the shape shown in the figure, including any rotated or reflected images.

(6 pont)

Deadline expired on April 12, 2021.

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

Megoldás. Tekintsük a tábla egy \(\displaystyle 100\times 99\)-es darabját, és azt osszuk fel \(\displaystyle 25\cdot 33=825\) darab \(\displaystyle 4\times 3\) méretű kis téglalapra. A skatulya-elv miatt van olyan kis téglalap, amelyből legfeljebb három négyzetet takarnak le a már lerakott L-tetrominók. Tekintsünk egy ilyen kis téglalapot. Megmutatjuk, hogy erre lehelyezthető még egy \(\displaystyle L\) tetrominó.

Két esetet vizsgálunk aszerint, hogy a középső mezők között van-e foglalt.

Ha a két középső mező közül van egy foglalt (mondjuk az 1. ábrán a felső, feketére színezett), akkor még legfeljebb két további mező lehet foglalt. Feltehető, hogy az ábrán látható piros és kék helyeken egy-egy mező foglalt, különben ezek valamelyikére letehetünk egy L-tetrominót. Így viszont az \(\displaystyle X\)-szel jelölt helyek valamelyike, és mindegyik sárga hely üres, így ismét lehelyezhető egy \(\displaystyle L\)-tetrominó.

Másodszor tegyük fel, hogy mindkét középső mező üres. Mivel a négy sarokból valamelyik biztosan szabad, így feltehető, hogy a második ábrán \(\displaystyle Y\)-nal jelölt mezők egyike (mondjuk a feketére festett) foglalt, különben az üres sarkot és a két középső mezőt használva letehetnénk egy L-tetrominót. Ekkor, az előzőekhez hasonlóan, a piros és a kék területeken egy-egy foglalt mező kell legyen, de így az "alsó" Y, és a jobb alsó sarok a két üres középső mezővel együtt befogad egy L-tetrominót. Ezzel minden esetet megvizsgáltunk, a bizonyítást befejeztük.

Statistics:

73 students sent a solution.
6 points:	52 students.
5 points:	2 students.
3 points:	1 student.
1 point:	4 students.
0 point:	9 students.
Unfair, not evaluated:	4 solutionss.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, March 2021