Problem K. 667. (October 2020)

K. 667. Start with a positive integer. In each move, take the half of the number if it is even, or add 1 to the number if it is odd. The sequence of moves terminates if it reaches the number 1.

\(\displaystyle a)\) Is it true that whatever the starting number is, it is always possible to reach 1 sooner or later (with a finite number of moves)?

\(\displaystyle b)\) Is it true that at most 30 moves are sufficient to reach 1 if we start from a four-digit number?

(6 pont)

Deadline expired on November 10, 2020.

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

Megoldás.

a) Ha a számunk az 1, akkor az 1-hez jutunk 0 lépésben.
Ha a számunk az 2, akkor az 1-hez jutunk 1 lépésben. (\(\displaystyle 2\rightarrow1\).)
Ha a számunk a 3, akkor az 1-hez jutunk 3 lépésben. (\(\displaystyle 3\rightarrow4\rightarrow2\rightarrow1\).)
Ha a számunk a 4, akkor az 1-hez jutunk 2 lépésben. (\(\displaystyle 4\rightarrow2\rightarrow1\).)
Ha a számunk az 5, akkor az 1-hez jutunk 5 lépésben. (\(\displaystyle 5\rightarrow6\rightarrow3\rightarrow4\rightarrow2\rightarrow1\).)
Ha a számunk a 6, akkor az 1-hez jutunk 4 lépésben. (\(\displaystyle 6\rightarrow3\rightarrow4\rightarrow2\rightarrow1\).)
Ha a számunk az 7, akkor az 1-hez jutunk 4 lépésben. (\(\displaystyle 7\rightarrow8\rightarrow4\rightarrow2\rightarrow1\).)
És így tovább.
Páros számból nála kisebb számhoz jutunk (a feléhez) egy lépésben, páratlan számból pedig a nála 1-gyel nagyobb szám feléhez jutunk 2 lépésben, így mindenképpen csökken az aktuális számunk 1 vagy 2 lépésben, vagyis előbb-utóbb eljutunk az 1-hez.

b) Próbáljuk ki pl. a 2018-at! \(\displaystyle 2018\rightarrow1009\rightarrow1010\rightarrow505\rightarrow506\rightarrow258\rightarrow129\rightarrow130\rightarrow\)
\(\displaystyle \rightarrow65\rightarrow66\rightarrow33\rightarrow34\rightarrow17\rightarrow18\rightarrow9\rightarrow10\rightarrow5\rightarrow6\rightarrow3\rightarrow4\rightarrow2\rightarrow1\).
Legrosszabb esetben kétlépésenként feleződik meg (kb.) a számunk (ilyenkor a felénél 0,5-del nagyobb számot kapunk), így mivel \(\displaystyle 213=8192<9999<214=16 384\), így legfeljebb 28 (27) lépés mindenképpen elegendő.

Keressünk meg visszafelé számolással egy hosszú lépést adó négyjegyű számot: \(\displaystyle 1\rightarrow2\rightarrow4\rightarrow3\rightarrow6\rightarrow5\rightarrow10\rightarrow9\rightarrow18\rightarrow17\rightarrow34\rightarrow33\rightarrow66\rightarrow65\rightarrow130\rightarrow129\rightarrow\)
\(\displaystyle \rightarrow258\rightarrow257\rightarrow514\rightarrow513\rightarrow1026\rightarrow \rightarrow1025\rightarrow2050\rightarrow2049\rightarrow4098\rightarrow4097\rightarrow8194\rightarrow8193\).

A 8193-ból kiindulva valóban 27 lépés kell.

Statistics:

138 students sent a solution.
6 points:	Barta Veronika, Biró Róza, Buday Noémi, Csima Borbála, Fórizs Emma, Gulyás Janka, Kéki Edit, Klusóczki-Bogdándi Alma, Kornya Gergely Csaba, Kuba Nikoletta, Mayer Krisztián, Mihalik Sára, Mód Péter Tamás, Schäffer Donát, Sebestyén József Tas, Töreczki Gábor, Várhegyi Hajnal Eszter.
5 points:	Bacsek Emma Borbála, Bakurek Máté, Biró Anna, Dancsák Dénes, Dukát Levente, Ecsédi Dániel, Emődi Marcell, Érdi Ferenc Vince, Farkas-Dancsházi Bálint, Gaspari Márton Samu, Görcsös Ákos Attila, Gyönki Dominik, Hajdu Márton, Heltovics Lilla, Jármai Roland, Kapuvári Márton, Kurucz Kitti, Laskai Botond, Lőrincz Panna, Markovics Áron, Markovics Benjámin, Molnár Kristóf, Simon Géza, Solymosi Csongor, Susán Henrik, Tarján Bernát, Tomesz László Gergő, Zsigószki Milán.
4 points:	12 students.
3 points:	15 students.
2 points:	20 students.
1 point:	19 students.
0 point:	18 students.
Unfair, not evaluated:	8 solutionss.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Mathematics of KöMaL, October 2020