A B. 4242. feladat (2010. február)

B. 4242. Létezik-e olyan n, amelyre a 4×n-es sakktábla bejárható egy huszárral úgy, hogy minden mezőre pontosan egyszer lépünk, majd az utolsó lépéssel visszaérkezünk a kiindulási helyre? Mi a helyzet abban az esetben, ha nem kell visszatérni a kiindulási helyre?

(4 pont)

A beküldési határidő 2010. március 10-én LEJÁRT.

Megoldás. Tegyük fel, hogy valamely \(\displaystyle n\)-re létezik egy ilyen bejárás, és rögzítsünk egy ilyet. Ekkor a szóban forgó \(\displaystyle 4\times n\)-es tábla minden mezőjének két szomszédja van: az egyik, ahonnan oda lépünk, a másik pedig ahová onnan lépünk; ezek az illető mezőtől eltérő sor(ok)ban helyezkednek el. A tábla mezőinek a sakktábláéhoz hasonló színezése mellett minden egyes mező szomszédai az adott mezőével ellentétes színűek. A két szélső sorban lévő \(\displaystyle 2n\) darab mező szomszédai mind a két középső sorba esnek, amivel mind a \(\displaystyle 4n\) szomszédságot át is tekintettük, vagyis a bejárás során nincsen olyan lépés, amely a két középső sor egyikéből a másikba történne. Ez azt jelenti, hogy minden második lépés után a huszár valamelyik szélső sorba, a többi lépés után pedig valamelyik középső sorba érkezik. Ennek megfelelően a bejárás során a huszár a szélső sorokban mindig ugyanolyan színű mezőre érkezik, a középső sorokban pedig azzal ellentétes színűre, ami nyilvánvaló ellentmondást jelent. Az első kérdésre tehát nemleges a válasz.

A második esetben viszont létezik ilyen \(\displaystyle n\), például \(\displaystyle n=5\). A \(\displaystyle 4\times 5\)-ös tábla lehetséges bejárását mutatja az alábbi ábra, melynek megtalálásában segíthet az előző gondolatmenet megfelelő módosítása.

Statisztika:

42 dolgozat érkezett.
4 pontot kapott:	Ágoston Péter, Cséke Balázs, Damásdi Gábor, Éles András, Gyarmati Máté, Halász Dániel, Hegedűs Csaba, Janzer Olivér, Karkus Zsuzsa, Kiss 902 Melinda Flóra, Korondi Zénó, Márkus Bence, Máthé László, Mester Márton, Mészáros András, Nagy 111 Miklós, Perjési Gábor, Réti Dávid, Szabó 928 Attila, Varnyú József, Zelena Réka.
3 pontot kapott:	Bogár Blanka, Janosov Milán, Kovács 235 Gábor, Repka 666 Dániel.
1 pontot kapott:	15 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2010. februári matematika feladatai