A B. 4881. feladat (2017. május)

B. 4881. Jelölje \(\displaystyle d(n)\) az \(\displaystyle n\) szám (pozitív) osztóinak számát. Mutassuk meg, hogy

\(\displaystyle n+d(1)+d(2)+\ldots+d(n)\le d(n+1)+d(n+2)+\ldots+d(2n). \)

(5 pont)

A beküldési határidő 2017. június 12-én LEJÁRT.

Megoldás. Az osztók összegét úgy is megkaphatjuk, hogy megnézzük melyik szám hányat oszt az \(\displaystyle 1,2,\dots,n\) számok, illetve az \(\displaystyle n+1,n+2,\dots,2n\) számok közül. A lehetséges osztók értéke csak \(\displaystyle 2n\)-nél nem nagyobb pozitív egész szám lehet, legyen tehát \(\displaystyle k\leq 2n\) egy pozitív egész szám. Az \(\displaystyle 1,2,\dots,n\) számok közül a \(\displaystyle k\) szám minden \(\displaystyle k\)-adikat osztja, vagyis a \(\displaystyle k\)-val oszthatók száma éppen \(\displaystyle \left[\frac{n}{k}\right]\). Ehhez hasonlóan az \(\displaystyle 1,2,\dots,2n\) számok között pontosan \(\displaystyle \left[\frac{2n}{k}\right]\) darab \(\displaystyle k\)-val osztható van, így \(\displaystyle k\) az \(\displaystyle n+1,n+2,\dots, 2n\) számok közül \(\displaystyle \left[\frac{2n}{k}\right]-\left[\frac{n}{k}\right]\) darabot oszt.

így a bal oldalon szereplő kifejezés

\(\displaystyle B:=n+d(1)+d(2)+\dots+d(n)=n+\sum\limits_{k=1}^{2n} \left[\frac{n}{k}\right]\)

alakban is írható, a jobb oldalon szereplő kifejezés pedig

\(\displaystyle J:=d(n+1)+d(n+2)+\dots+d(2n)=\sum\limits_{k=1}^{2n} \left(\left[\frac{2n}{k}\right] - \left[\frac{n}{k}\right] \right).\)

Mivel az \(\displaystyle 1,2,\dots,n\) számoknak nem lehet \(\displaystyle n\)-nél nagyobb osztója, ezért valójában

\(\displaystyle B=n+\sum\limits_{k=1}^{n} \left[\frac{n}{k}\right]\)

is igaz. Ha \(\displaystyle n<k\leq 2n\), akkor \(\displaystyle k\) az \(\displaystyle n+1,n+2,\dots,2n\) számok közül pontosan egynek osztója, vagyis a

\(\displaystyle J=n+\sum\limits_{k=1}^{n} \left(\left[\frac{2n}{k}\right] - \left[\frac{n}{k}\right] \right)\)

összefüggés is teljesül. Vagyis a bizonyítandó \(\displaystyle B\leq J\) egyenlőtlenség pontosan akkor teljesül, ha

\(\displaystyle \sum\limits_{k=1}^{n} \left[\frac{n}{k}\right]\leq \sum\limits_{k=1}^{n} \left(\left[\frac{2n}{k}\right] - \left[\frac{n}{k}\right] \right),\)

azaz, ha

\(\displaystyle 0\leq \sum\limits_{k=1}^{n} \left(\left[\frac{2n}{k}\right] - 2\left[\frac{n}{k}\right] \right).\)

Ez az egyenlőtlenség valóban teljesül, hiszen a jobb oldalon szereplő összeg minden tagja nemnegatív, ugyanis a

\(\displaystyle \left[\frac{2n}{k}\right] \geq 2\left[\frac{n}{k}\right]\)

egyenlőtlenség speciális esete a tetszőleges valós \(\displaystyle x,y\) számokra fennálló \(\displaystyle [x]+[y]\leq [x+y]\) egyenlőtlenségnek.

Statisztika:

36 dolgozat érkezett.
5 pontot kapott:	Ardai István Tamás, Baran Zsuzsanna, Borbényi Márton, Csahók Tímea, Csuha Boglárka, Daróczi Sándor, Döbröntei Dávid Bence, Fülöp Anna Tácia, Gáspár Attila, Győrffy Ágoston, Imolay András, Janzer Orsolya Lili, Kerekes Anna, Kővári Péter Viktor, Mikulás Zsófia, Nagy Nándor, Németh 123 Balázs, Noszály Áron, Saár Patrik, Schrettner Jakab, Simon Dániel Gábor, Szabó 417 Dávid, Szabó Kristóf, Tiszay Ádám, Tóth Viktor, Török Ádám, Vári-Kakas Andor, Várkonyi Dorka, Weisz Máté.
4 pontot kapott:	Deák Bence.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	3 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2017. májusi matematika feladatai