Az A. 882. feladat (2024. május)

A. 882. Legyen $\displaystyle H_1$, $\displaystyle H_2$, $\displaystyle \ldots$, $\displaystyle H_m$ a pozitív egész számok nemüres részhalmazai, legyen továbbá $\displaystyle S$ ezen halmazok uniója. Bizonyítsuk be, hogy

$\displaystyle \sum_{i=1}^m \sum_{a, b\in H_i} (a,b) \ge \frac{1}{m} \sum_{a, b\in S} (a, b),$

ahol $\displaystyle (a,b)$ az $\displaystyle a$ és $\displaystyle b$ legnagyobb közös osztóját jelöli.

(A $\displaystyle \sum_{(a,b)\in X}$ azt jelöli, hogy a szumma az olyan $\displaystyle (a, b)$ rendezett párokon fut végig, amikre $\displaystyle a\in X$ és $\displaystyle b\in X$.)

Javasolta: Matolcsi Dávid (Berkeley)

(7 pont)

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

Megoldás. Felhasználjuk az Euler-féle $\displaystyle \varphi$ függvényre vonatkozó jól ismert állítást:

$\displaystyle \sum_{d|n} \varphi(d)=n.$

Ezt felhasználva

$\displaystyle \sum_{a, b\in S} (a, b) = \sum_{a,b\in S} \sum_{d|(a,b)} \varphi(d) = \sum_{a,b\in S}\sum_{d|a,d|b}\varphi(d),$

hiszen pontosan azok a számok osztják $\displaystyle a$-t és $\displaystyle b$-t is, melyek osztják a legnagyobb közös osztójukat. Ezek után figyeljük meg, hogy egy adott $\displaystyle \varphi(d)$ annyiszor szerepel a szummában, ahányféle módon ki lehet választani két többszörösét $\displaystyle S$-ből: ez pedig nyilvánvalóan $\displaystyle S_d^2$, ahol $\displaystyle S_d$ az $\displaystyle S$ halmaz $\displaystyle d$-vel osztható elemeinek számát jelöli. Így tehát

$\displaystyle \sum_{a, b\in S} (a, b)=\sum_{d=1}^{\infty} \varphi(d) S_d^2$

Jelölje $\displaystyle H_{i,d}$ a $\displaystyle H_i$ halmaz $\displaystyle d$-vel osztható elemeinek számát. Ekkor a számtani-négyzetes közép közti egyenlőtlenséget alkalmazva az $\displaystyle H_{i,d}$ számokra ($\displaystyle d$ rögzített, $\displaystyle i$ a változó):

$\displaystyle \frac{\sum_{i=1}^m H_{i,d}^2}{m} \ge \left(\frac{\sum_{i=1}^{m}H_{i,d}}{m}\right)^2\ge \frac{S_d^2}{m^2},$

azaz $\displaystyle m$-mel szorozva

$\displaystyle \sum_{i=1}^m H_{i,d}^2\ge \frac{S_d^2}{m}.$

A fenti egyenlőtlenséget $\displaystyle \varphi(d)$-vel megszorozva és minden $\displaystyle d$-re összeadva megkapjuk a bizonyítandót:

$\displaystyle \sum_{i=1}^{m} \sum_{a,b\in H_i}(a,b)=\sum_{i=1}^m\sum_{d=1}^{\infty} \varphi(d)H_{i,d}^2 = \sum_{d=1}^{\infty}\sum_{i=1}^m\varphi(d)H_{i,d}^2\ge \sum_{d=1}^{\infty}\varphi(d)\frac{S_d^2}{m} = \frac{1}{m}\sum_{a,b\in S}(a,b),$

és ezzel a bizonyítást befejeztük.

Statisztika:

8 dolgozat érkezett.
7 pontot kapott:	Szakács Ábel, Varga Boldizsár.
6 pontot kapott:	Forrai Boldizsár.
5 pontot kapott:	1 versenyző.
3 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.
0 pontot kapott:	1 versenyző.

A KöMaL 2024. májusi matematika feladatai