Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

A K. 173. feladat (2008. szeptember)

K. 173. A sakktáblán a lehető legrövidebb úton (a legkevesebb lépéssel) C5-ről H2-re szeretnénk eljutni lóval (lólépésben). Hány lépésből áll a legkisebb lépésszámú út? Adjunk meg 12 ilyen utat.

(6 pont)

A beküldési határidő 2008. október 10-én LEJÁRT.


Megoldás. Állítsuk elő az összes lehetséges útvonalat! Az X-szel jelzett mezőről indulva kell az Y-nal jelzett mezőre eljutni. Mivel mindkét mező fehér, ezért páros számú lépés szükséges az úthoz. Két lépés nem elegendő, hiszen ezzel csak a G sorba tudnánk eljutni, négy lépéses utat viszont könnyen találhatunk, így 4 a minimális lépésszám.

A lólépés során minden egyes lépéssel egy vagy két sorral közeledünk vagy távolodunk a célmezőhöz, ugyanez vonatkozik az oszlopokra is. Mivel Y öt sorral feljebb van, mint X, ezért a sorok szerinti közeledést vagy távolodást tekintve 2+1+1+1 vagy 2+2+2-1 kombinációban állítható elő egy ilyen négy lépéses út. A számsor végén azonban -1 nem állhat, mert ekkor a H utáni nem létező sorba kéne kerülnünk, így a sorok szerinti haladásra összesen 4+3 lehetőséget kapunk (figyelembe véve a számok sorrendjét is). Mivel Y három oszloppal balra van X-hez képest, ezért az oszlopok szerinti közeledést vagy távolodást tekintve 1+1+2-1 vagy 1+2+2-2 kombinációban állítható elő egy ilyen négy lépéses út. A számsor végén azonban -2 nem állhat, mert ekkor az 1. oszlop előtti nem létező oszlopba kéne kerülnünk, így az oszlopok szerinti haladásra összesen 4+3 lehetőséget kapunk (figyelembe véve a számok sorrendjét is). Ha a sorok szerint 1-et távolodunk vagy közeledünk, akkor az oszlopok szerint 2-t, a lólépés jellegéből fakadóan, és fordítva. Ennek megfelelően az alábbi párokat tudjuk képezni a sor-oszlop szerinti közeledést-távolodást figyelembe véve:

Tehát 18 lehetséges négylépéses útvonal van, ezeket a táblázat tartalmazza.


Statisztika:

267 dolgozat érkezett.
6 pontot kapott:Antal Viktória, Bende Lilla, Béres Zoltán, Budafoki Dóra, Budavári Ruben Pál, Csikós Alexandra, Forrai Bálint, Gróf Gábor, Halász 423 Dániel, Halász Dániel, Hímer Gréta, Horváth Kinga, Horváth Kristóf, Jászberényi Tünde, Kakasi Dávid, Kasó Márton, Kis Máté, Kisznyér Csaba, Konkoly 002 Csaba, Kovács Flóra, Kovalcsik Anna, Könye Viktor, Kővágó Zoltán, Nagy 014 Gergely, Nagy Bálint György, Nagy Olivér, Nagy Tamás, Nánási József, Németh Alex, Reskó Sándor, Samu Viktor, Sándor Tímea, Sápi András, Serfőző Virág Fanni, Simonics Zsófia, Solti Bálint, Straubinger Dániel, Szabó Olivér, Szécsényi 136 Andrea, Szilárd Péter, Szőts Nóra, Tran Minh Hieu, Varjú János, Veres Andrea, Zagyva Dániel, Zentai Kinga, Zolcsák Ádám.
5 pontot kapott:34 versenyző.
4 pontot kapott:113 versenyző.
3 pontot kapott:27 versenyző.
2 pontot kapott:11 versenyző.
1 pontot kapott:17 versenyző.
0 pontot kapott:5 versenyző.
Nem versenyszerű:13 dolgozat.

A KöMaL 2008. szeptemberi matematika feladatai