 |
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