Feladat: N.13 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Becsei András ,  Csörnyei Marianna ,  Dienes Péter ,  Erdélyi László ,  Futó Gábor ,  Gyarmati Katalin ,  György András ,  Megyesi Zoltán ,  Pap Gyula ,  Pete Gábor ,  Sági Krisztián 
Füzet: 1994/december, 501 - 502. oldal  PDF file
Témakör(ök): Egységgyökök, Sokszög lefedések, Nehéz feladat
Hivatkozás(ok):Feladatok: 1993/december: N.13

Bizonyítsuk be, hogy egy n×m-es tábla akkor és csak akkor fedhető le (egyrétűen) k×1-es dominókkal, ha a lefedés azonos állású dominókkal is elvégezhető (azaz ha km vagy kn).

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.

I. megoldás. A feladat ,,csak akkor'' részét bizonyítjuk, a másik irány úgyis nyilvánvaló. Tegyük fel indirekt módon, hogy k sem az n-et, sem az m-et nem osztja, és az n×m-es táblát mégis le tudtuk fedni k×1-es dominókkal. Legyen n=ak+b és m=ck+d, ahol a,b,c,d egészek és 0<b,d<k. Számozzuk be a tábla mezőit az első k darab természetes számmal oly módon, hogy az i. sor j. mezőjére (i+j-2)-nek k-val vett osztási maradékát írjuk. (1. ábra). Világos, hogy a fedésben részt vevő dominók midegyike k darab különböző számot fed le, függetlenül attól, hogy vízszintes vagy függőleges helyzetben van. Ezért a táblán miden szám ugyanannyiszor fordul elő. A táblából vágjunk le jobbról egy (ak)×m nagyságú részt, ekkor minden szám előfordulását ugyanannyival csökkentettük, hiszen a levágott rész lefedhető k×1-es dominókkal. Mivel a maradék b×m-es táblán ugyanannyiszor szerepel minden szám, azért ha ebből alulról még egy b×(ck)-as részt is levágunk, akkor a fennmaradó b×d nagyságú táblán is ugyanannyiszor szerepelnek a számok 0-tól (k-1)-ig. Megmutatjuk, hogy ez nem igaz. Az általánosságnak nem megy rovására, ha felteszzük, hogy 0<db<k. Ekkor a b-1 szám minden sorban szerepel, tehát pontosan d darab van belőle a táblán, a második sorban azonban nem szerepel a 0, tehát 0-ból legfeljebb d-1 darab lehet a táblán (2. ábra). Ellentmondásra jutottunk, ami a feladatbeli állítást igazolja.
II. megoldás. Az előző megoldás ötletét komplex számokkal ötvözve még gyorsabban célhoz érhetünk. Legyen ugyanis ε=cos(2π/k)+isin(2π/k) az első k-adik egységgyök, és tegyük fel, hogy az n×m-es táblát lefedtük k×1-es dominókkal. Ha a tábla mezőit oly módon töltjük ki komplex számokkal, hogy az r. sor s. mezőjére az εr+s-2 egységgyököt írjuk, akkor minden k×1-es dominó a k. egységgyökök egy teljes rendszerét fedi le, amelyeknek 0 az összegük. Így a táblán lévő összes egységgyökök is 0-t adnak összegül, azaz

0=1rn1smεr+s-2=(r=1nεr-1)(s=1mεs-1)=1-εn1-ε1-εm1-ε.

Az egyenlőség két oldalát összehasonlítva kapjuk, hogy εn=1 vagy εm=1, azaz kn vagy km.