Feladat: Gy.3015 Korcsoport: 16-17 Nehézségi fok: átlagos
Megoldó(k):  Balogh Attila ,  Barát Anna ,  Benedek Csaba ,  Bérczi Gergely ,  C. Szabó István ,  Dedinszky Zsófia ,  Gueth Krisztián ,  Győri Nikolett ,  Hajdufi Péter ,  Juhász András ,  Kis-Tóth Ágnes ,  Lippner Gábor ,  Naszódi Gergely ,  Németh Viktor Péter ,  Nyul Gábor ,  Pásztor Aurél ,  Patakfalvi Zsolt ,  Pozsonyi Gergő ,  Serény András ,  Terpai Tamás ,  Tóth Ádám ,  Zubcsek Péter Pál 
Füzet: 1996/május, 278 - 279. oldal  PDF file
Témakör(ök): Sakk, Konstruktív megoldási módszer, Gyakorlat
Hivatkozás(ok):Feladatok: 1995/november: Gy.3015

A sötét király az n×m-es sakktábla bal felső sarkán áll. Ketten a következő játékot játsszák: felváltva lépnek a királlyal, de mindig csak olyan (csúcsban vagy oldalban szomszédos) mezőre, ahol addig még nem járt. Az veszít, aki nem tud lépni. Kinek van nyerő stratégiája?

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.

Azt fogjuk bizonyítani, hogy ha nm páros, akkor a kezdő játékosnak van nyerő stratégiája, míg ha nm páratlan, akkor a másodiknak. Tekintsük először a páros esetet.
Mivel nm páros, azért n és m közül legalább az egyik páros, legyen ez például az n. Ekkor az n×m-es tábla felosztható 2×1-es résztéglalapokra, az 1. ábrán látható módon. A kezdő első lépése legyen a2. Ezután a táblára fennáll a következő fontos tulajdonság:

be nem járt része csupa még nem érintett  2×1-es téglalapból áll.(*)
Bárhova lépjen is a második játékos, a megfelelő téglalap másik mezője még szabad, így a kezdő oldaléphet, és ezzel a (*) tulajdonság is megmarad.
Ha tehát a kezdő végig ezt a stratégiát követi, akkor biztosan ő nyer: a másik játékos tetszőleges lépése után ő tud még lépni, viszont a táblán véges sok mező van, így előbb-utóbb a másik játékos már nem léphet sehová sem.
Vizsgáljuk most a másik esetet, vagyis amikor n és m mindegyike páratlan. Ekkor a táblát a 2. ábra szerint osztjuk résztéglalapokra. Látható, hogy a tábla ismét rendelkezik a (*) tulajdonsággal; így bármit is lépjen a kezdő, a második játékos a megfelelő téglalap másik mezőjébe léphet, amivel a (*) tulajdonság is helyreáll. A már előbb látott gondolatmenet mutatja, hogy ez a stratégia biztosítja a második játékos számára a győzelmet.