A K. 876. feladat (2025. november)

K. 876. Gondolj egy pozitív egész számra. Ha a szám páros, akkor oszd el \(\displaystyle 2\)-vel, ha páratlan, akkor adj hozzá \(\displaystyle 1\)-et. Az eredménnyel ugyanígy folytasd: ha a szám páros, akkor oszd el kettővel, ha páratlan, akkor adj hozzá \(\displaystyle 1\)-et. Igaz-e, hogy ha egy \(\displaystyle 2025\)-nél kisebb számból indulunk ki, akkor kevesebb, mint \(\displaystyle 25\) lépésben az \(\displaystyle 1\)-hez jutunk?

(5 pont)

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

Megoldás. Vegyük a \(\displaystyle 2\) nemnegatív egész kitevőjű hatványait 2025-ig. (1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024). Ezek a (határ)számok 12 részre osztják az 1–2025 számhalmazt. (1, 2, 3–4, 5–8, 9–16, 17–32, 33–64, 54–128, 129–256, 257–512, 513–1024, 1025–2025.) Ha valamikor is kettőhatványt kapunk a lépéseink során, akkor onnan egyenes út vezet az 1-hez. \(\displaystyle 2^n\)-ből \(\displaystyle n\) lépéssel az 1-hez jutunk.

Ha éppen nem 2-hatványnál vagyunk, hanem két szomszédos (1-nél nagyobb) 2-hatvány között valahol, akkor, ha a szám páros, egy lépéssel (:2) az eggyel korábbi két 2-hatvány közé jutunk, ha pedig páratlan a szám, akkor két lépésben jutunk ugyanide. Így mivel legfeljebb 2 lépésben eggyel korábbi részbe jutunk, így legfeljebb \(\displaystyle 2\cdot12=24\) lépésben az 1-hez jutunk, tehát az állítás igaz.

Statisztika:

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

A KöMaL 2025. novemberi matematika feladatai