KöMaL - Középiskolai Matematikai és Fizikai Lapok
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum

Rendelje meg a KöMaL-t!

Kifordítható

tetraéder

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

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 points)

Deadline expired on 10 May 2011.


Google Translation (Sorry, the solution is published in Hungarian only.)

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 on problem B. 4360.
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

  • Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
    MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley