Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem B. 4881. (May 2017)

B. 4881. Let \(\displaystyle d(n)\) denote the number of (positive) factors of the number \(\displaystyle n\). Prove that

\(\displaystyle n+d(1)+d(2)+\cdots +d(n)\le d(n+1)+d(n+2)+\dots +d(2n). \)

(5 pont)

Deadline expired on June 12, 2017.


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

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.


Statistics:

36 students sent a solution.
5 points: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 points:Deák Bence.
3 points:1 student.
2 points:3 students.
1 point:1 student.
0 point:1 student.

Problems in Mathematics of KöMaL, May 2017