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 B. 4360. feladat (2011. április)

B. 4360. Tetszőleges n pozitív egész szám esetén jelölje S(n) az n számjegyeinek összegét. Milyen 1-nél nagyobb k egészekhez létezik olyan ck pozitív valós szám, melyre

S(kn)\geck.S(n)

teljesül minden pozitív egész n esetén?

Javasolta: Erben Péter (Budapest)

(5 pont)

A beküldési határidő 2011. május 10-én LEJÁRT.


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.


Statisztika:

10 dolgozat érkezett.
5 pontot kapott:Á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 pontot kapott:Zsakó András.
0 pontot kapott:1 versenyző.

A KöMaL 2011. áprilisi matematika feladatai