A B. 5426. feladat (2024. december)

B. 5426. Ugri, a szöcske a számegyenes pozitív egész számain ugrál úgy, hogy mindegyiket pontosan egyszer látogatja meg. Lehetséges-e, hogy ugrásainak hosszai között minden pozitív egész pontosan egyszer szerepel?

Javasolta: Lovas Márton (Budakalász)

(5 pont)

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

Megoldás. Igen. Induljon Ugri az \(\displaystyle 1\)-ről, és kövesse az alábbi stratégiát:

Kétféle "üzemmódja" lehet Ugrinak: száméhsége és távolságéhsége. Amikor száméhes, akkor megkeresi a legkisebb olyan \(\displaystyle k\) számot, melyen még nem járt, és a jelenlegi tartózkodási helyéről, \(\displaystyle n\)-ről átugrik \(\displaystyle N\)-re, majd át \(\displaystyle k\)-ra. Ehhez egy olyan nagy \(\displaystyle N\geq n,k\) számot választ, hogy \(\displaystyle N-n\) és \(\displaystyle N-k\) is nagyobb legyen bármely eddigi ugrásánál, \(\displaystyle N\) pedig nagyobb legyen minden eddigi érintett számnál. \(\displaystyle k\)-ra megérkezve távolságéhessé válik.

Amikor Ugri távolságéhes, megkeresi a legkisebb olyan \(\displaystyle d\) távolságot, mely még nem szerepel ugrásai hosszai között, és \(\displaystyle n\)-ről átugrik \(\displaystyle n+M\)-re, onnan pedig \(\displaystyle n+M+d\)-re. Ehhez \(\displaystyle d\lt M\)-et oly nagynak választja, hogy \(\displaystyle M\) nagyobb legyen minden eddigi ugrásánál, és \(\displaystyle n+M\) (és így \(\displaystyle n+M+d\) is) nagyobb legyen minden eddigi meglátogatott számnál. A művelet végén száméhessé válik.

A fenti konstrukcióból látható, hogy sem az érintett számok, sem a távolságok között nem lehet ismétlődés, valamint minden számhoz, illetve távolsághoz előbb-utóbb eljut Ugri, hiszen minden száméhségnél, illetve távolságéhségnél a legkisebb kihagyott szám, illetve távolság legalább \(\displaystyle 1\)-gyel nő.

Statisztika:

51 dolgozat érkezett.
5 pontot kapott:	Ali Richárd, Aravin Peter, Bolla Donát Andor, Görömbey Tamás, Holló Martin, Klement Tamás, Kovács Benedek Noel, Minh Hoang Tran, Miszori Gergő, Molnár István Ádám, Pázmándi József Áron, Péter Hanna, Prohászka Bulcsú, Rajtik Sándor Barnabás, Sárdinecz Dóra, Szabó 721 Sámuel, Tamás Gellért, Török Eszter Júlia, Vámosi Bendegúz Péter, Varga 511 Vivien, Virág Lénárd Dániel, Vödrös Dániel László, Wágner Márton.
4 pontot kapott:	Balla Ignác .
3 pontot kapott:	2 versenyző.
2 pontot kapott:	4 versenyző.
1 pontot kapott:	6 versenyző.
0 pontot kapott:	14 versenyző.

A KöMaL 2024. decemberi matematika feladatai