A B. 4973. feladat (2018. szeptember)

B. 4973. Legyenek \(\displaystyle a_1, a_2, \ldots, a_{2018}\) olyan nemnegatív valós számok, amelyek összege \(\displaystyle 1\). Adjuk meg az

\(\displaystyle S = \sum_{i \ne j,\; i\mid j} a_ia_j \)

összeg lehető legnagyobb értékét.

(Argentin feladat alapán)

(6 pont)

A beküldési határidő 2018. október 10-én LEJÁRT.

Megoldás. A fő észrevétel az, hogy ha \(\displaystyle i\mid j\) (de \(\displaystyle i\ne j\)), akkor \(\displaystyle i\) prímosztóinak száma kisebb, mint \(\displaystyle j\) prímosztóinak száma (a prímtényezőket multiplicitással számolva).

Ezen észrevétel segítségével először megmutatjuk, hogy a legnagyobb \(\displaystyle S\) érték úgy is elérhető, ha \(\displaystyle a_i=0\) minden olyan \(\displaystyle i\)-re, ami nem 2-hatvány (az 1-et is 2-hatványnak tekintjük).

Ha \(\displaystyle 1\leq i\leq 2018\), akkor \(\displaystyle i\) prímosztóinak száma \(\displaystyle 0,1,2,\dots,10\) lehet, hiszen 2 a legkisebb prím, és \(\displaystyle 2^{11}>2018\). Legyenek \(\displaystyle a_1,a_2,\dots,a_{2018}\) tetszőleges nemnegatív valós számok, melyek összege 1. Ha \(\displaystyle 1\leq i\leq 2018\) egy 2-hatvány, akkor legyen \(\displaystyle a_i'\) az olyan \(\displaystyle a_i\) számok összege, melyeknek éppen annyi prímosztója van (multiplicitással számolva), mint \(\displaystyle i\)-nek. Tehát \(\displaystyle a_1'=a_1\), \(\displaystyle a_2'=\sum\limits_{1\leq i\leq 2018, i\text{ prím}} a_i\), és így tovább... Ha \(\displaystyle i\) nem 2-hatvány, akkor legyen \(\displaystyle a_i'=0\). Az így kapott \(\displaystyle a_1',a_2',\dots,a_{2018}'\) nemnegatív számok összege is 1. Megmutatjuk, hogy az \(\displaystyle S':=\sum\limits_{i\ne j,i\mid j} a_i'a_j'\) összeg legalább akkora, mint az eredeti \(\displaystyle S=\sum\limits_{i\ne j,i\mid j} a_ia_j\) összeg. Használni fogjuk az \(\displaystyle \Omega(m)\) jelölést, ami az \(\displaystyle m\) egész szám prímtényezőinek száma multiplicitással számolva, vagyis \(\displaystyle \Omega(m)\) az \(\displaystyle m\) szám prímtényezős felbontásában a kitevők összege. Az \(\displaystyle S\leq S'\) egyenlőtlenség formális igazolása:

\(\displaystyle S=\sum\limits_{i\ne j,i\mid j} a_ia_j\leq \sum\limits_{\Omega(i)<\Omega(j)} a_ia_j = \sum\limits_{0\leq \alpha<\beta\leq 10} \sum\limits_{\Omega(i)=\alpha,\Omega(j)=\beta} a_ia_j=\)

\(\displaystyle =\sum\limits_{0\leq \alpha<\beta \leq 10 } \sum\limits_{\Omega(i)=\alpha} a_i\sum\limits_{\Omega(j)=\beta}a_j= \sum\limits_{0\leq \alpha<\beta \leq 10 } a_{2^\alpha}'a_{2^\beta}'=S'.\)

Ugyanezt úgy is elképzelhetjük, hogy az \(\displaystyle a_i'\) számok helyére beírogatva a megfelelő \(\displaystyle a_i\)-k összegét, majd a zárójeleket felbontva az olyan \(\displaystyle a_ia_j\) (\(\displaystyle i<j\)) szorzatok összegét kapjuk, ahol \(\displaystyle \Omega(i)<\Omega(j)\), míg eredetileg ezen nemnegatív szorzatoknak csak egy része alkotta az \(\displaystyle S\) összeget: azok, amelyekre \(\displaystyle i\mid j\) is fennáll.

Tehát feltehetjük, hogy \(\displaystyle a_1',a_2',a_4',a_8',\dots,a_{1024}'\) kivételével a többi szám értéke 0. Vezessük be a \(\displaystyle b_i=2^{i-1}\) jelölést \(\displaystyle 1\leq i\leq 11\) mellett, ezzel a jelöléssel \(\displaystyle S'=\sum\limits_{1\leq i<j\leq 11} b_ib_j\) legnagyobb értékét keressük \(\displaystyle b_1+b_2+\dots +b_{11}=1\), \(\displaystyle 0\leq b_1,\dots,b_{11}\) feltételek mellett. Mivel \(\displaystyle 2S'+b_1^2+\dots+b_{11}^2=(b_1+\dots+b_{11})^2=1\), ezért \(\displaystyle S'\) akkor maximális, ha \(\displaystyle b_1^2+\dots+b_{11}^2\) minimális. A számtani és négyzetes közepek közötti egyenlőtlenség szerint azonban \(\displaystyle \frac{1}{11}\leq\frac{b_1+\dots+b_{11}}{11}\leq \sqrt{\frac{b_1^2+\dots+b_{11}^2}{11}}\), amiből \(\displaystyle b_1^2+\dots+b_{11}^2\geq \frac{1}{11}\). Tehát \(\displaystyle 1-2S'\geq\frac{1}{11}\), és így \(\displaystyle S'\leq \frac{5}{11}\).

Ezzel bebizonyítottuk, hogy \(\displaystyle S\leq S'\leq \frac{5}{11}\). Ugyanakkor, ha \(\displaystyle a_1=a_2=a_4=\dots=a_{1024}=\frac{1}{11}\) (és a többi szám értéke 0), akkor \(\displaystyle S=S'=\frac{5}{11}\), tehát \(\displaystyle S\) legnagyobb lehetséges értéke \(\displaystyle \frac{5}{11}\).

Megjegyzés. A megoldás alapján az is meghatározható, hogy \(\displaystyle S=\frac{5}{11}\) milyen esetekben érhető el, ennek végiggondolását az érdeklődő Olvasóra bízzuk.

Statisztika:

37 dolgozat érkezett.
6 pontot kapott:	Beke Csongor, Dobák Dániel, Füredi Erik Benjámin, Győrffy Ágoston, Hegedűs Dániel, Jedlovszky Pál, Márton Dénes, Molnár Bálint, Nagy Nándor, Szabó 417 Dávid, Tóth 827 Balázs, Tubak Dániel, Várkonyi Zsombor, Weisz Máté.
5 pontot kapott:	Argay Zsolt, Kerekes Anna, Noszály Áron, Tóth-Rohonyi Iván.
4 pontot kapott:	7 versenyző.
3 pontot kapott:	3 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.
0 pontot kapott:	7 versenyző.

A KöMaL 2018. szeptemberi matematika feladatai