Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

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:

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


A KöMaL 2020. októberi matematika feladatai