 |
Az A. 492. feladat (2009. november) |
A. 492. Tetszőleges, pozitív egész számokból álló, nem üres \(\displaystyle H\) halmazra jelöljük \(\displaystyle \mathrm{lnko}(H)\)-val a \(\displaystyle H\) elemeinek legnagyobb közös osztóját. Mutassuk meg, hogy ha \(\displaystyle A\) pozitív egész számokból álló, véges, nem üres halmaz, akkor
\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{lnko}(H) > 0. \)
(5 pont)
A beküldési határidő 2009. december 10-én LEJÁRT.
Megoldás. Legyenek \(\displaystyle A\) elemei \(\displaystyle a_1<a_2<\dots<a_n\), egy közös többszörösük \(\displaystyle T\).
Felhasználjuk, hogy tetszőleges \(\displaystyle u\) pozitív egészre
| \(\displaystyle \sum_{d|u} \varphi(d) = u. \) | \(\displaystyle (1) \) |
(Most nem lesz szükségünk a \(\displaystyle \varphi\) függvény további számelméleti tulajdonságaira, csak arra, hogy az értéke mindig pozitív.)
Legyen tetszőleges \(\displaystyle u\) pozitív egész és \(\displaystyle 1\le i \le n\) esetén
\(\displaystyle \chi_i(u) = \left\{\matrix{ 1 & \mathrm{ha~} u|a_i, \cr 0 & \mathrm{ha~} u\not|a_i. \cr}\right. \)
Ekkor
\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{lnko}(H) = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \mathrm{lnko}(a_{i_1},\ldots,a_{i_k}) = \)
\(\displaystyle = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \sum_{u|\mathrm{lnko}(a_{i_1},\ldots,a_{i_k})} \varphi(u) = \)
\(\displaystyle = \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \sum_{u|T} \varphi(u) \cdot \big(\chi_{i_1}(u)\cdot\ldots\cdot\chi_{i_k}(u)\big) = \)
\(\displaystyle = \sum_{u|T} \varphi(u) \left( -\frac12 \sum_{k=1}^n ~ \sum_{1\le i_1<\ldots<i_k\le n} \big(-2\chi_{i_1}(u)\big)\cdot\ldots\cdot\big(-2\chi_{i_k}(u)\big) \right) = \)
\(\displaystyle = \sum_{u|T} \varphi(u) \frac{ 1 - \big(1-2\chi_1(u)\big)\cdot\ldots\cdot \big(1-2\chi_n(u)\big)}{2}. \)
Az utolsó összegben az \(\displaystyle \frac{1-\big(1-2\chi_1(u)\big)\cdot\ldots\cdot \big(1-2\chi_n(u)\big)}{2}\) értéke \(\displaystyle 1\) vagy \(\displaystyle 0\), attól függően, hogy az \(\displaystyle u\) szám az \(\displaystyle a_1,\dots,a_n\) számok közül páratlan soknak, vagy pedig páros soknak osztója.
Mivel az \(\displaystyle a_n\) szám nem lehet osztója \(\displaystyle a_1,\dots,a_{n-1}\) egyikének sem, az \(\displaystyle u=a_n\) esetben \(\displaystyle \frac{1-\big(1-2\chi_1(u)\big)\cdot\ldots\cdot \big(1-2\chi_n(u)\big)}{2}=1\), és így
\(\displaystyle \sum_{\emptyset\ne H\subseteq A} {(-2)}^{|H|-1} \mathrm{lnko}(H) \ge \varphi(a_n) > 0. \)
Megjegyzések. 1. Az állítást (és a megoldást) nem nehéz átírni halmazokra: Tetszőleges \(\displaystyle X_1,X_2,\dots,X_n\) véges, nem üres halmazok esetén
| \(\displaystyle \sum_{k=1}^n \sum_{1\le i_1<\ldots<i_k\le n} (-2)^{k-1} \Big| X_{i_1} \cap\ldots\cap X_{i_k} \Big| \ge 0. \) | \(\displaystyle (2) \) |
A baloldalon álló összeg az olyan elemeknek a száma, amelyek az \(\displaystyle X_1,\ldots,X_n\) halmazok közül páratlan soknak elemei. (Itt tehát egyenlőség is fennállhat.)
Ha tetszőleges \(\displaystyle x\) számhoz, amelynek prímtényezős felbontása \(\displaystyle x=p_1^{t_1}\cdot\ldots\cdot p_k^{t_k}\), hozzárendeljük a \(\displaystyle p_1^{p_1^{t_1}-1}\cdot\ldots\cdot p_k^{p_k^{t_k}-1}\) szám pozitív osztóinak halmazát, a feladat állítását visszavezethetjük a (2) egyenlőtlenségre.
2. Az (1) képlet bizonyítása például az
\(\displaystyle (1,u), (2,u), \dots, (u,u) \)
számsorozat vizsgálatával történhet. A sorozat minden eleme egész és osztója \(\displaystyle u\)-nak, és minden egyes \(\displaystyle d\)-re az \(\displaystyle u/d\) szám pontosan \(\displaystyle \varphi(d)\)-szer szerepel a sorozatban.
Statisztika:
6 dolgozat érkezett. 5 pontot kapott: Backhausz Tibor, Bodor Bertalan, Éles András, Nagy 235 János, Nagy 648 Donát. 4 pontot kapott: Strenner Péter.
A KöMaL 2009. novemberi matematika feladatai