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

(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

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