Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A B. 5161. feladat (2021. március)

B. 5161. A \(\displaystyle 100\times 100\)-as sakktáblára letettünk \(\displaystyle 800\) L-tetrominót. Mutassuk meg, hogy letehetünk még egy L-tetrominót a táblára. A tetrominók nem fednek át, és mindegyik pontosan a sakktábla \(\displaystyle 4\) mezőjét fedi. L-tetrominó alatt az ábrán látható alakzatot, elforgatottjait és tükrözöttjeit értjük.

(6 pont)

A beküldési határidő 2021. április 12-én LEJÁRT.


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.


Statisztika:

A B. 5161. feladat értékelése még nem fejeződött be.


A KöMaL 2021. márciusi matematika feladatai