Feladat: Gy.3201 Korcsoport: 14-15 Nehézségi fok: nehéz
Megoldó(k):  Bárány Kristóf ,  Devecsery András ,  Fehér Lajos Károly ,  Gelencsér Gábor ,  Gyenes Zoltán ,  Győri Nikolett ,  Harangi Viktor ,  Juhász András ,  Keszegh Balázs ,  Kiss Gergely ,  Kunszenti-Kovács Dávid ,  Máthé András ,  Papp Dávid ,  Pesti Gábor ,  Szabadka Zoltán ,  Szabó Péter ,  Székelyhidi Gábor ,  Terpai Tamás ,  Tóth Ágnes ,  Varjú Péter ,  Végh A. László 
Füzet: 1999/január, 29 - 30. oldal  PDF  |  MathML 
Témakör(ök): Lefedések, Rekurzív sorozatok, Logikai feladatok, Gyakorlat
Hivatkozás(ok):Feladatok: 1998/április: Gy.3201

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.

9×9-es helyett általában olyan ,,sakktáblán'' bizonyítjuk az állítást, amelynek oldalai (a mezők élhosszában mérve) páratlan hosszúságúak. Vezessünk be egy a sakkjátékban használatoshoz hasonló koordinátarendszert a tábla mezőinek jelölésére; eszerint a ,,bal alsó'' mező koordinátái (1,1), az eggyel fölötte levőé (1,2) stb.
Szemeljük ki az egyik lefedő dominót, és jelöljük a két négyzetét 1-gyel és 2-vel (1. ábra). Az ábrán *-gal jelöltük meg azt a dominónkkal élszomszédos egyetlen mezőt, amelynek az 1-es mezővel nincs közös csúcsa. Ha ez nem éppen az üres sarok, akkor őt pontosan egy dominó fedi le. Nevezzük ezt a kiszemelt dominó rákövetkezőjének, és számozzuk a *-gal jelölt mezőjét 1-gyel, a másikat 2-vel.

 

(1) A továbbiakban megmutatjuk, hogy ha egy olyan dominót szemelünk ki, amely a tábla egyik sarkát ‐ pl. az (1,1) koordinátájút ‐ fedi le, és a saroknál lévő mezője az 1-es, akkor képezve ennek rákövetkezőjét, a rákövetkező rákövetkezőjét stb., végül az üres sarok lesz az eljárásban *-gal jelölendő mező, amelynél a dominók eme sorozatának képzése szükségképpen megakad.
Ha állításunkkal szemben nem ez a helyzet, akkor a láncban mindegyik dominónak van rákövetkezője, és egyszer olyan dominót kapunk rákövetkezőként, amely már korábban előfordult a sorozatban; a 2. ábra ábrázolja azt a helyzetet, amikor ez az ismétlődés először bekövetkezik.
A rákövetkezési sorrendben ,,kört'' alkotó dominókból álló alakzatot foglaljuk bele abba a legkisebb téglalapba, amelynek oldalai az eredeti tábla éleivel párhuzamosak (az ábrán ez a vastag vonallal határolt téglalap).
Mivel a dominók részeinek számozása összhangban van a sakktábla szokásos színezésével (pl. az 1-es mezők mindig fehérek, a 2-esek pedig feketék), azért az ábrából látható, hogy a befoglaló téglalap mindkét oldala páratlan hosszúságú, ezért a ‐ mezőkben mért ‐ területe páratlan. Ebből a területből kivonva a ─ jellel ellátott téglalapok összterületét, a dominók által közrezárt területhez jutunk. Világos, hogy a dominók páros mérőszámú területet fednek le, hiszen mindegyik dominó területe 2 egység. Látható továbbá, hogy a dominók alkotta ,,töröttvonal'' töréspontjai mindig 1-es jelű mezőben vannak, ezért a levonandó téglalapok területe páros (szemköztes csúcsaik azonos színűek). Ezzel azt kaptuk, hogy a dominókör által bekerített (az ábrán vonalkázással jelölt) rész páratlan sok mezőt tartalmaz. Így lennie kell a bekerített részen olyan mezőnek, amelyet nem fed le dominó. Ez azonban lehetetlen, mivel mindegyik belső mező le van fedve (egyedül az egyik sarok fedetlen). Az (1) állítást ezzel igazoltuk.
Jelölje ezután D1, D2, ..., Dt azt a dominósorozatot, amelyben D1 1-es mezője az (1,1) sarok, Di rákövetkezője Di+1 (i=1, 2, ..., t-1), és Dt-nek nem létezik rákövetkezője, azaz (az 1. ábra jelöléseivel) Dt 2-es jelű mezőjének *-gal jelölendő élmenti szomszédja a tábla egyetlen fedetlen sarokmezője. Így Dt eltolható úgy, hogy az eredetileg Dt által lefedett 1-es mező legyen üres. Az eljárást ezzel az üres mezővel és Dt-1-gyel folytatjuk, s.í.t.; végül (1,1) lesz fedetlen.
 Máthé András (Budapest, ELTE Apáczai Csere J. Gimn., 10. o.t.)