Problem B. 4973. (September 2018)

B. 4973. Let \(\displaystyle a_1, a_2, \ldots, a_{2018}\) denote non-negative real numbers that add up to \(\displaystyle 1\). Find the largest possible value of the sum \(\displaystyle S = \sum_{i \ne j,\; i\mid j} a_ia_j\).

Based on an Argentinean problem

(6 pont)

Deadline expired on October 10, 2018.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

37 students sent a solution.
6 points:	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 points:	Argay Zsolt, Kerekes Anna, Noszály Áron, Tóth-Rohonyi Iván.
4 points:	7 students.
3 points:	3 students.
2 points:	1 student.
1 point:	1 student.
0 point:	7 students.

Problems in Mathematics of KöMaL, September 2018