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 c_k pozitív valós szám, melyre

S(kn)c_k^.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