Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?
I want the old design back!!! :-)

Problem B. 4360. (April 2011)

B. 4360. Let S(n) denote the sum of the digits for any positive integer n. For what integers k greater than 1 is there a positive real number ck such that S(kn)\geck.S(n) for all positive integers n?

(Suggested by P. Erben, Budapest)

(5 pont)

Deadline expired on May 10, 2011.


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

Megoldás. A feladatnak \(\displaystyle k=1\) esetén is van értelme, ekkor \(\displaystyle c_1=1\) megfelelő lesz. Ha a \(\displaystyle k\) számhoz \(\displaystyle c_k\), az \(\displaystyle \ell\) számhoz \(\displaystyle c_\ell\) megfelelő, akkor a \(\displaystyle k\ell\) számhoz \(\displaystyle c_{k\ell}=c_kc_\ell\) megfelelő lesz, hiszen minden \(\displaystyle n\) pozitív egész szám esetén

\(\displaystyle S((k\ell)n)=S(k(\ell n))\ge c_k\cdot S(\ell n)\ge c_k\cdot(c_\ell\cdot S(n))=(c_kc_\ell)\cdot S(n).\)

Megmutatjuk, hogy \(\displaystyle k=2\) és \(\displaystyle k=5\) esetén \(\displaystyle c_2=c_5=1/9\) megfelelő lesz, amiből rögtön adódik, hogy ha a \(\displaystyle k\) számnak nincsen a 2-től és az 5-től különböző prímosztója, akkor \(\displaystyle k\)-hoz létezik megfelelő \(\displaystyle c_k\) pozitív szám. Az \(\displaystyle n\) számjegyeinek száma szerinti indukcióval fogjuk megmutatni, hogy \(\displaystyle S(2n)\) és \(\displaystyle S(5n)\) értéke is legalább \(\displaystyle S(n)/9\). Ez nyilvánvaló, ha \(\displaystyle n\) egyjegyű szám, sőt \(\displaystyle n=0\) esetén is igaz. Tegyük fel, hogy a legfeljebb \(\displaystyle t\) jegyű számokra az állítást már beláttuk, és legyen \(\displaystyle n\) egy \(\displaystyle t+1\) jegyű szám, amelynek első számjegye \(\displaystyle b\), az annak elhagyásával keletkező legfeljebb \(\displaystyle t\) jegyű szám (ami 0 is lehet) pedig \(\displaystyle m\). Ekkor \(\displaystyle S(n)=b+S(m)\le S(m)+9\). Ezért az indukciós feltevés értelmében elég annyit megmutatni, hogy \(\displaystyle S(2n)\ge S(2m)+1\), illetve \(\displaystyle S(5n)\ge S(5m)+1\), hiszen ebből már

\(\displaystyle S(2n)\ge S(2m)+1\ge \frac{S(m)}{9}+1=\frac{S(m)+9}{9}\ge \frac{S(n)}{9}\)

és

\(\displaystyle S(5n)\ge S(5m)+1\ge \frac{S(m)}{9}+1=\frac{S(m)+9}{9}\ge \frac{S(n)}{9}\)

következik. Gondoljuk meg, hogy \(\displaystyle 2n\) illetve \(\displaystyle 5n\) utolsó \(\displaystyle t\) számjegye megegyezik \(\displaystyle 2m\), illetve \(\displaystyle 5m\) utolsó \(\displaystyle t\) számjegyével, viszont \(\displaystyle 2n\) és \(\displaystyle 5n\) is legalább \(\displaystyle t+1\) jegyű szám. Ezért ha \(\displaystyle 2m\) legfeljebb \(\displaystyle t\) jegyű szám, az \(\displaystyle S(2n)\ge S(2m)+1\) egyenlőtlenség nyilvánvaló, és ugyanígy látszik, hogy \(\displaystyle S(5n)\ge S(5m)+1\), ha \(\displaystyle 5m\) legfeljebb \(\displaystyle t\) jegyű. Ha a \(\displaystyle 2m\) számnak \(\displaystyle t+1\) jegye van, akkor az első számjegy 1. Ekkor a \(\displaystyle 2n\) szám utolsó \(\displaystyle t\) jegyét elhagyva a \(\displaystyle 2b+1\) számot kapjuk, melynek jegyeinek összege legalább 2, így az \(\displaystyle S(2n)\ge S(2m)+1\) egyenlőtlenség most is könnyen látszik. Hasonlóképpen, ha az \(\displaystyle 5m\) számnak \(\displaystyle t+1\) jegye van, akkor az első számjegy nem nagyobb, mint 4, legyen ez \(\displaystyle c\). Ha az \(\displaystyle 5n\) szám utolsó \(\displaystyle t\) jegyét elhagyjuk, akkor az \(\displaystyle 5b+c\) számot kapjuk. Ennek utolsó jegye \(\displaystyle c\) vagy \(\displaystyle c+5\). A második esetben az erősebb \(\displaystyle S(5n)\ge S(5m)+5\) egyenlőtlenség is fennáll. Az első eset pedig \(\displaystyle b\ge 1\) miatt csak úgy fordulhat elő, ha \(\displaystyle 5b+c\) legalább kétjegyű. Ekkor viszont \(\displaystyle S(5b+c)\ge c+1\) miatt jutunk az ígért \(\displaystyle S(5n)\ge S(5m)+1\) egyenlőtlenségre.

Jegyezzük meg még a következőt. Ha \(\displaystyle k\) számnak nincsen a 2-től és az 5-től különböző prímosztója, akkor található hozzá olyan \(\displaystyle k'\) szám amelynek szintén nincs 2-től és 5-től különböző prímosztója, és \(\displaystyle kk'\) 10-nek egész kitevős hatványa: \(\displaystyle kk'=10^s\). Ekkor minden \(\displaystyle n\) pozitív egészre \(\displaystyle S(n)=S(10^sn)\ge c_{k'}\cdot S(kn)\), vagyis \(\displaystyle S(kn)\le (c_{k'})^{-1} \cdot S(n)\) is teljesül.

A továbbiakban megmutatjuk, hogy a fentieken kívül semilyen más \(\displaystyle k>1\) egészhez nem létezik megfelelő \(\displaystyle c_k\) konstans. Írjuk fel a \(\displaystyle k\) számot \(\displaystyle k=gh\) alakban, ahol a \(\displaystyle g>1\) egész szám nem osztható sem 2-vel, sem 5-tel, a \(\displaystyle h\) egész számnak pedig nincsen 2-től és 5-től különböző prímosztója. Elegendő lesz megmutatni azt, hogy tetszőlegesen kicsi \(\displaystyle \alpha>0\) számhoz található olyan \(\displaystyle n\) pozitív egész, amelyre \(\displaystyle S(gn)< \alpha\cdot S(n)\), hiszen ekkor \(\displaystyle S(kn)\le (c_{h'})^{-1}\alpha\cdot S(n)\) is teljesül, ami azt jelenti, hogy tetszőlegesen kicsi \(\displaystyle \beta>0\) számhoz található olyan \(\displaystyle n\) pozitív egész, amelyre \(\displaystyle S(kn)< \beta\cdot S(n)\), ami kizárja megfelelő \(\displaystyle c_k\) konstans létezését.

Mivel a \(\displaystyle g\) szám 10-hez relatív prím, az Euler--Fermat tétel szerint található hozzá olyan \(\displaystyle G\) pozitív egész, hogy \(\displaystyle gG+1=10^{\varphi(g)}\). Ekkor tetszőlegesen nagy \(\displaystyle N\) pozitív egész szám esetén

\(\displaystyle 10^{N\varphi(g)}+(g-1)= \sum_{i=0}^{N-1}10^{i\varphi(g)}(10^{\varphi(g)}-1)+g =g\cdot \left(\sum_{i=0}^{N-1}10^{i\varphi(g)}G+1\right)=gn.\)

Itt \(\displaystyle 0<G,G+1<10^{\varphi(g)}\) miatt egyrészt \(\displaystyle S(n)=(N-1)\cdot S(G)+S(G+1)\ge N\), másrészt \(\displaystyle S(gn)=1+S(g-1)\). Ezért \(\displaystyle N>(1+S(g-1))/\alpha\) esetén \(\displaystyle S(gn)<\alpha\cdot S(n)\) valóban teljesülni fog.


Statistics:

10 students sent a solution.
5 points:Ágoston Péter, Damásdi Gábor, Dolgos Tamás, Nagy Róbert, Perjési Gábor, Strenner Péter, Viharos Andor, Zilahi Tamás.
4 points:Zsakó András.
0 point:1 student.

Problems in Mathematics of KöMaL, April 2011