Problem K. 876. (November 2025)

K. 876. Think of a positive integer. If the number is even, divide it by 2, if odd, add 1 to it. Continue in the same manner with the result: if it's even, divide it by 2, if it's odd, add 1 to it. Is it true that if the initial number is less than 2025, we will get 1 in less than 25 steps?

(5 pont)

Deadline expired on December 10, 2025.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

141 students sent a solution.
5 points:	95 students.
4 points:	6 students.
3 points:	4 students.
2 points:	7 students.
1 point:	23 students.
0 point:	6 students.

Problems in Mathematics of KöMaL, November 2025