Feladat: 2003. évi Nemzetközi Matematika Diákolimpia 13. feladata Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Rácz Béla András 
Füzet: 2004/október, 389 - 391. oldal  PDF file
Témakör(ök): Egybevágósági transzformációk, Sík parkettázás, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):Feladatok: 2004/szeptember: 2003. évi Nemzetközi Matematika Diákolimpia 13. feladata

Nevezzük horognak az alábbi ábrán látható, hat egységnégyzetből álló alakzatot
 
 
valamint minden olyan alakzatot, amely ebből forgatásokkal és tükrözésekkel kapható.
Határozzuk meg az összes olyan m×n-es téglalapot, ami lefedhető horgokkal úgy, hogy
a lefedés hézagmentes és átfedések nélküli,
semelyik horognak nem nyúlik semelyik része sem a téglalapon kívülre.

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.

Rácz Béla András megoldása. Feltehetjük, hogy egy lefedett téglalap m, n oldalai egészek, illetve hogy minden horog éppen hat egységnégyzetet fed le, amelyek szerepelnek az egész téglalap egységnégyzetekre bontásában.*

 

 
1. ábra
 

Tekintsünk egy horgot és a hozzá tartozó ,,középső'' mezőt (1. ábra). Ez a mező a lefedni kívánt téglalap belsejében van, egy másik horognak tehát le kell fednie. Könnyen ellenőrizhető, hogy ez csak kétféle módon lehetséges (2a., 2b. ábra).
 
 

Az egymás ,,közepét'' kölcsönösen lefedő két horgot ,,összeragasztva'' kétféle 12 területű csempét kapunk: a 3×4-es téglalapot és ennek ,,ferde'' formáját. A téglalap területe, mn tehát osztható 12-vel, hiszen a lefedésben nyilván egész számú csempe vesz részt. Így 3m vagy 3n. Az általánosság megszorítása nélkül föltehető, hogy 3m. Vizsgáljuk most már azt, hogy m, illetve n a 2-nek milyen hatványával osztható.
(I) 4m, azaz 12m.
Ha n=1 vagy 2, akkor a lefedés nyilván lehetetlen, ha n=3 vagy 4, akkor a téglalap már 3×4-es csempékkel is lefedhető (3. ábra).
 

 
3. ábra
 

Ha n=5, akkor a két ,,szomszédos'' sarokmezőt két különböző csempe fedi csak le, ezek viszont nem férnek el átfedés nélkül (4. ábra).
 

 
4. ábra
 

Ha n6, akkor ‐ 12m esetén ‐ az n×m-es téglalap lefedhető 3×4-es csempékkel. Ha ugyanis n=3α+4β, ahol α,βN, akkor a megfelelő lefedés az 5. ábrán látható. Ha pedig n6, akkor létezik a megfelelő felbontás, hiszen 6=3+3, 7=3+4, 8=4+4, végül ha n előáll ilyen alakban, akkor nyilván n+3 is.
 

 
5. ábra
 

Vegyük észre, hogy lényegében újra igazoltuk a már tárgyalt n=3,4 eseteket.
(II) Ha 4n, akkor a lefedés nyilván megvalósítható 3×4-es csempékkel (6. ábra).
 

 
6. ábra
 

(III) Ha sem (I) sem pedig (II) nem teljesül, azaz 4m és 4n, akkor 4mn miatt m is és n is páros. Azt állítjuk, hogy ilyenkor a megfelelő lefedésben szükségképpen páros sok csempe vesz részt és így a téglalap területe osztható 8-cal. Ez viszont nem lehetséges, ha egyik oldal hossza sem osztható 4-gyel, így ilyenkor nincs megfelelő lefedés.
Színezzük ki a lefedett téglalap mezőit úgy, hogy minden negyedik oszlop fekete legyen, a többi pedig fehér. Ekkor a fekete mezők száma páros, hiszen minden oszlopban páros sok mező van. Csoportosítsuk a lefedésben részt vevő csempéket a 7. ábra szerint.
 

 
7. ábra
 

Minden ,,álló'' csempe páros sok fekete mezőt fed le, egy-egy fekvő csempe pedig páratlan sokat (3-at), ezért páros sok ,,fekvő'' csempe vesz részt a lefedésben. Ha pedig az oszlopok helyett minden negyedik sort színezünk feketére, akkor ugyanígy kapjuk, hogy az ,,álló'' csempék száma páros.
Így tehát összesen is páros számú csempe van, a megfelelő lefedés ebben az esetben nem létezik.
Összefoglalva: a lehetséges m és n értékek a következők:
 3m  és  4n; és szimmetrikusan  3n  és  4m; 12m  és  n6;   12n  és  m6.

 
Megjegyzések. 1. Az adott felsorolásban bizonyos (m;n) számpárok többször is előfordulhatnak.
2. Látható, hogy a ,,ferde'' csempéket nem tudjuk hasznosítani, ami egyáltalán lefedhető, ahhoz elegendőek a 3×4-es csempék is.
*Ennek bizonyítását az értékelés során nem várták el a versenyzőktől; maga a bizonyítás nem nehéz, inkább technikai jellegű.