Feladat: F.3197 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Bíró Zsuzsanna ,  Csikvári András ,  Dályay Virág ,  Gajári Dávid ,  Gyenes Zoltán ,  Győri Nikolett ,  Hangya Balázs ,  Hesz Gábor ,  Hesz Zoltán ,  Juhász András ,  Keszegh Balázs ,  Kunszenti-Kovács Dávid ,  Lippner Gábor ,  Páles Csaba ,  Pogány Ádám ,  Sarlós Ferenc ,  Taraza Busra ,  Terpai Tamás ,  Végh A. László ,  Zábrádi Gergely 
Füzet: 1999/április, 225 - 226. oldal  PDF file
Témakör(ök): Sakk, Feladat
Hivatkozás(ok):Feladatok: 1997/november: F.3197

Egy 8×8-as sakktábla mezőin bábukat helyeztünk el úgy, hogy minden egyes sorban és oszlopban pontosan 4 bábu van. Bizonyítsuk be, hogy kiválasztható 8 bábu úgy, hogy közülük semelyik kettő nincs egy oszlopban vagy egy sorban.

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.

Induljunk el egy olyan mezőről, amelyiken áll bábu. Haladjunk vízszintesen az ugyanazon sorban lévő második bábuig, innen folytassuk utunkat függőleges irányban addig, amíg bábuhoz nem érünk.
Ezután forduljunk a most elért sorban lévő másik bábu felé, ha pedig ezt is elértük, az ezzel egy oszlopban álló bábu felé induljunk, és így tovább. Vándoroljunk addig, amíg el nem érkezünk a kiindulási mező oszlopához. Mivel minden sorban és oszlopban ugyanannyi bábu áll, erre előbb-utóbb sor kerül.
Ekkor térjünk vissza a kiindulási ponthoz.
Nevezzünk egy ilyen utat körútnak. Két körutat diszjunktnak mondunk, ha nincs olyan bábu, amely mindkét útban szerepel.
Vegyük most diszjunkt körutak egy maximális rendszerét. Ezek együttesen az összes bábut lefedik. Ellenkező esetben ugyanis a körutakból kimaradó bábuk száma minden oszlopban és sorban páros, mert mindegyik körút minden oszlopból és sorból csak páros számú bábut tartalmazhat. Ez viszont azt jelenti, hogy ha csak a körutakból kimaradó bábukat tekintjük, akkor még mindig találhatunk a sakktáblán körutat. Ez a körút pedig nyilván diszjunkt az eddigiektől, a kiválasztott körútrendszer tehát nem lehetett maximális.
Tekintsünk tehát egy maximális körútrendszert. Színezzünk mindegyik körútban minden második bábut kékre, a többit pedig pirosra. Mint már említettük, egy körút minden oszlopból és sorból csak páros számú bábut tartalmazhat, ezért minden oszlopban és sorban pontosan annyi piros bábu van, mint kék.
Hagyjuk el ezután a sakktábláról a piros bábukat. Ekkor minden sorban és oszlopban pontosan 2 bábu marad.
Ezeket a bábukat körutakra fűzve és közülük ismét minden másodikat elhagyva valóban elérhetjük, hogy minden sorban és oszlopban pontosan egy bábu álljon. Ezzel a feladatot megoldottuk.

 Taraza Busra (Budapest, Apáczai Cs. J. Gyak. Gimn., 10. o.t.)