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  |  MathML 
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

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, m⋅n tehát osztható 12-vel, hiszen a lefedésben nyilván egész számú csempe vesz részt. Így 3∣m vagy 3∣n. Az általánosság megszorítása nélkül föltehető, hogy 3∣m. Vizsgáljuk most már azt, hogy m, illetve n a 2-nek milyen hatványával osztható.
(I) 4∣m, azaz 12∣m.
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 n≥6, akkor ‐ 12∣m 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 n≥6, 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 4∣n, 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 4∤m és 4∤n, akkor 4∣mn 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:
• 3∣m  és  4∣n; és szimmetrikusan • 3∣n  és  4∣m;• 12∣m  és  n≥6;  • 12∣n  és  m≥6.

 
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ű.