A B. 4686. feladat (2015. január)

B. 4686. A sík egész koordinátájú rácspontjain egy bolha ugrál. Tud-e úgy ugrálni, hogy minden rácspontban pontosan egyszer járjon, az ugrásainak a hossza pozitív egész szám legyen és minden pozitív egész pontosan egyszer forduljon elő az ugrások hosszai között?

(6 pont)

A beküldési határidő 2015. február 10-én LEJÁRT.

Megoldási ötlet: Legyen két listánk: azokról a távolságokról, amit még nem használtunk és azokról a pontokról, ahol még nem jártunk.

Megoldás. Számozzuk meg a sík rácspontjait valamilyen módon, például ,,csigavonalban''.

Csak vízszintes vagy függőleges irányban lépkedünk majd, így a lépések hossza mindig egész szám lesz.

Most nézzünk meg egy lépéssort. Első lépésben próbáljunk meg akkora hosszt lépni, amely eddig nem volt, s ezek közül a legkisebb. Ezt úgy csináljuk, hogy kilépünk az eddigi pontokat lefedő téglalapból egy olyan hosszal, ami még nem volt, majd továbblépünk az eddig nem szerepelt legkisebb szakasszal.

Második lépésben próbáljunk rálépni a legkisebb sorszámú pontra, amire még nem álltunk rá. Ezt úgy tehetjük meg, hogy először ráállunk arra az oszlopra, ahol ez a szám van, úgy, hogy kilépünk olyan messzire, ahol még nem voltunk egy minden eddiginél nagyobb lépéssel, s utána visszalépünk a kívánt oszlopba (ennek a lépésnek a hossza is így megfelelően nagy lesz). Ezután elléphetünk a kívánt mezőre. (Amennyiben azzal a hosszal már léptünk, akkor felfele lépünk akkorát, ami minden eddiginél nagyobb, s úgy lépünk a mezőre).

Így minden lépéshossz pontosan egyszer fog szerepelni, és minden mezőre rálépünk.

Nagy Kartal (Budapesti Fazekas Mihály Gyakorló Általános Iskola és Gimnázium, 11. évf.)

Statisztika:

22 dolgozat érkezett.
6 pontot kapott:	Andó Angelika, Baran Zsuzsanna, Fekete Panna, Molnár-Sáska Zoltán, Nagy Kartal, Schwarcz Tamás, Szebellédi Márton, Williams Kada.
5 pontot kapott:	Döbröntei Dávid Bence, Khayouti Sára.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	2 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	2 versenyző.

A KöMaL 2015. januári matematika feladatai