Problem B. 5395. (May 2024)

B. 5395. Let \(\displaystyle d(k)\) denote the number of positive divisors of a positive integer \(\displaystyle k\), and let \(\displaystyle 1<n\) be an integer. Which sum is larger: \(\displaystyle d(2)+d(4)+\dots+d(2n)\) or \(\displaystyle (d(1)+d(3)+\dots+d(2n-1))+(d(1)+d(2)+\dots+d(n))\)?

(Proposed by Péter Pál Pach, Budapest)

(5 pont)

Deadline expired on June 10, 2024.

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

Megoldás. Legyen

\(\displaystyle S:=\sum\limits_{i=1}^{2n}(-1)^id(i)=d(2n)-d(2n-1)+d(2n-2)-d(2n-3)+\dots+d(2)-d(1).\)

Az \(\displaystyle S\) alternáló összeget kiszámolhatjuk úgy is, hogy az \(\displaystyle 1,2,\dots,2n\) számok (pozitív) osztóira nézzük meg, összességében melyiket hányszor számoljuk. Legyen tehát \(\displaystyle 1\leq k\leq 2n\) tetszőleges. Ha \(\displaystyle k=2K\) páros, akkor páratlan többszöröse nincsen, így az \(\displaystyle S\) összegben csak pozitív előjellel számoljuk, éspedig összesen \(\displaystyle \lfloor \frac{2n}{2K} \rfloor = \lfloor \frac{n}{K} \rfloor\)-szer. Így \(\displaystyle S\)-hez a páros osztók hozzájárulása \(\displaystyle \sum\limits_{K=1}^n \lfloor \frac{n}{K} \rfloor\). Vegyük észre, hogy ez éppen annyi, mint \(\displaystyle d(1)+d(2)+\dots+d(n)\), hiszen utóbbi összeghez egy \(\displaystyle 1\leq K\leq n\) osztó hozzájárulása összesen szintén éppen \(\displaystyle \lfloor \frac{n}{K} \rfloor\).

Legyen most \(\displaystyle 1\leq k\leq 2n\) páratlan. Ekkor \(\displaystyle k\) többszörösei felváltva páratlan és páros számok, ha \(\displaystyle 2n\)-ig páros sok többszöröse van, akkor \(\displaystyle S\)-hez 0-val járul hozzá, ha pedig páratlan sok, akkor \(\displaystyle (-1)\)-gyel (hiszen a többöszörösök, vagyis \(\displaystyle k\), \(\displaystyle 2k\), \(\displaystyle 3k\), \(\displaystyle \dots\) közül az első páratlan).

Az eddigiek alapján \(\displaystyle S-(d(1)+d(2)+\dots+d(n))\) éppen az olyan \(\displaystyle 1\leq k\leq 2n\) páratlan számok számának \(\displaystyle (-1)\)-szerese, melyeknek \(\displaystyle 2n\)-ig páratlan sok többszörösük van, vagyis amelyekre \(\displaystyle \lfloor \frac{2n}{k} \rfloor\) páratlan. Világos, hogy \(\displaystyle k=2n-1\) például ilyen, hiszen \(\displaystyle 2(2n-1)=4n-2>2n\) az \(\displaystyle n>1\) feltétel miatt. Így \(\displaystyle S-(d(1)+d(2)+\dots+d(n))<0\), ami éppen azt jelenti, hogy a kérdéses összegek közül a második, vagyis \(\displaystyle (d(1)+d(3)+\dots+d(2n-1))+(d(1)+d(2)+\dots+d(n))\) a nagyobb.

Statistics:

36 students sent a solution.
5 points:	Aravin Peter, Bodor Mátyás, Bui Thuy-Trang Nikolett, Csató Hanna Zita , Fekete Aron, Forrai Boldizsár, Gyenes Károly, Hodossy Réka, Holló Martin, Keresztély Zsófia, Kovács Benedek Noel, Sági Mihály, Sárdinecz Dóra, Sütő Áron, Wágner Márton.
4 points:	Csupor Albert Dezső, Jármai Roland, Kerekes András, Lakner Hanna, Szabó 721 Sámuel, Vigh 279 Zalán.
2 points:	6 students.
1 point:	2 students.
0 point:	7 students.

Problems in Mathematics of KöMaL, May 2024