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+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 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:

A B. 5426. feladat értékelése még nem fejeződött be.

A KöMaL 2024. decemberi matematika feladatai