Feladat: N.18 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Braun Gábor ,  Burcsi Péter ,  Csörnyei Marianna ,  Dienes Péter ,  Elek Péter ,  Futó Gábor ,  Megyesi Zoltán ,  Pap Gyula ,  Szeidl Ádám 
Füzet: 1994/december, 503 - 504. oldal  PDF file
Témakör(ök): Sakktáblával kapcsolatos feladatok, Bolyongási feladatok, Maradékos osztás, Legnagyobb közös osztó, Nehéz feladat
Hivatkozás(ok):Feladatok: 1994/január: N.18

Egy n×k mezős sakktáblán egy futó vándorol. A futó az egyik világos színű sarokból indul, és átlós irányban halad. Amikor a tábla szélére ér, ,,visszaverődik''. A mozgást akkor fejezi be, amikor ismét egy sarokba ér. Milyen (n,k) számpárok esetén igaz, hogy a futó az öszes világos színű mezőt bejárja?

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.

Foglalkozzunk csak a k,n>1 esettel. (k=1 vagy n=1 esetén a feladat értelmetlen.) Számozzuk a tábla sorait 0-tól (k-1)-ig, oszlopait 0-tól (n-1)-ig úgy, hogy a bal felső sarok legyen a (0,0) mező. Tegyük fel továbbá, hogy a futó innen indul, tehát ez a mező világos színű. Nem nehéz észrevenni, hogy x lépés után a futó helyzete csak az x-nek (2k-2)-vel és (2n-2)-vel való osztási maradékától függ. Pontosabban, ha x±p (mod 2n-2), ahol p=0,1,2,...,n-1, akkor a futó a |p|. oszlopban van, és jobbra vagy balra tart aszerint, hogy a p-nek pozitív vagy negatív előjelet adtunk (azzal a megállapodással, hogy a 0-hoz pozitív, az (n-1)-hez negatív előjelet társítunk; ezekben az esetekben ugyanis mindkét előjel ugyanazt a maradékosztályt határozza meg). Hasonlóan, ha x±q (mod 2k-2), akol q=1,2,...,k-1, akkor a futó a |q|. sorban van, és lefelé vagy felfelé tart aszerint, hogy a q-nek milyen előjelet adtunk (a 0-hoz pozitív, a (k-1)-hez negatív előjelet társítva). A (p,q) mező pontosan akkor világos, ha p-q páros. Így a futó akkor és csak akkor járja be az összes világos mezőt, ha az u(2n-2)±p=v(2k-2)±q egyenletnek minden szóba jövő (p,q) párra van egészekből álló (u,v) megoldása. (Megoldáson azt értjük, hogy a bal és a jobb oldalon az előjeleket alkalmasan választva fennáll az egyenlőség.) Mivel ±p±q páros, azért az egyenletet, továbbra is az egészek között maradva, ilyen alakba írhatjuk: ±p±q2=v(k-1)-u(n-1). Ha k-1 és n-1 relatív prímek, akkor az egyenlet persze mindig megoldható, függetlenül az előjelek választásától. Ha azonban p-t 2-nek, q-t 0-nak választjuk, akkor az is látható, hogy ez a feltétel valójában szükséges is a megoldás létezéséhez.
Tehát a futó pontosan akkor járja be az összes világos színű mezőt a táblán, ha (n-1,k-1)=1.

Szeidl Ádám (Miskolc, Földes F. Gimn., IV. o. t.) és
Braun Gábor (Bp., Szent István Gimn., I. o. t.) dolgozata alapján