A K. 667. feladat (2020. október)

K. 667. Induljunk ki egy pozitív egész számból. Egy lépésben, ha az aktuális számunk páros, akkor vegyük a felét, ha pedig páratlan, adjunk hozzá 1-et. A lépéseknek akkor van vége, ha el tudunk jutni az 1-hez.

\(\displaystyle a)\) Igaz-e, hogy bármelyik számból kiindulva előbb-utóbb (véges sok lépésben) az 1-hez jutunk?

\(\displaystyle b)\) Igaz-e, hogy legfeljebb 30 lépésben jutunk az 1-hez, ha egy négyjegyű számból indulunk ki?

(6 pont)

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

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.

Statisztika:

138 dolgozat érkezett.
6 pontot kapott:	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 pontot kapott:	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 pontot kapott:	12 versenyző.
3 pontot kapott:	15 versenyző.
2 pontot kapott:	20 versenyző.
1 pontot kapott:	19 versenyző.
0 pontot kapott:	18 versenyző.
Nem versenyszerű:	8 dolgozat.
Nem számítjuk a versenybe a születési dátum vagy a szülői nyilatkozat hiánya miatt:	1 dolgozat.

A KöMaL 2020. októberi matematika feladatai