Feladat: F.2381 Korcsoport: 16-17 Nehézségi fok: átlagos
Füzet: 1983/április, 148 - 149. oldal  PDF file
Témakör(ök): Sakktáblával kapcsolatos feladatok, Konstruktív megoldási módszer, Feladat
Hivatkozás(ok):Feladatok: 1982/október: F.2381

Egy 2n×2n-es sakktáblára 3n bábut tettünk fel. Mutassuk meg, hogy el lehet hagyni n sort és n oszlopot úgy, hogy a megmaradó n×n-es sakktáblán egyetlen bábu se maradjon.

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.

Megadunk egy módszert a mondott tulajdonságú n sor és n oszlop kiválasztására. Válasszuk ki a sorok közül azt, amelyiken legtöbb bábu áll, és hagyjuk el. (Ha több ilyen sor van, ezek bármelyikét választhatjuk.) Ezt ismételjük addig, amíg n sor marad.
Ha az elhagyott n sor mindegyikén legalább két bábu állt, akkor legalább 2n bábut hagytunk el, s így a megmaradt n×2n-es táblán legfeljebb n bábu áll. Ha pedig az utoljára elhagyott soron legfeljebb egy bábu áll, akkor a megmaradó n sor mindegyikén is legfeljebb egy bábu állhat, hiszen eljárásunk során mindig a legtöbb bábut tartalmazó sort hagytuk el ‐ s így ebben az esetben is legfeljebb n bábu áll a megmaradó n×2n-es táblán. Legfeljebb n bábut pedig n oszlop elhagyásával nyilván eltüntethetünk. Ezzel a feladat állítását bizonyítottuk.

 

Megjegyzés. Igen sok versenyző értette félre a feladat szövegét és azt "bizonyította'', hogy el lehet helyezni 3n bábut úgy, hogy utána n sor és n oszlop a mondott módon elhagyható legyen. Ezek a dolgozatok 0 pontot kaptak.
Szintén sokan estek abba a hibába, hogy valamilyen speciális elhelyezésről állították, hogy az elhagyások szempontjából ez a "legkedvezőtlenebb''. Ezek a dolgozatok hiányosnak minősültek, és általában 2‐3 pontot kaptak.