argentina tst 2009

[exodd]

siano $ \displaystile{a_1,a_2,a_3,...,a_{300}} $ 300 numeri reali non negativi tali che la loro somma sia 1

trovare il massimo valore possibile della sommatoria degli $ \displaystile{a_ia_j} $ con i diverso da j e tali che $ \displaystile{i|j} $

p.s. 400°post!

[jordan]

Se $ (x,y) \in \mathbb{N}^2 $ t.c. $ 1\le x<y\le 300 $ e $ x \nmid y $ allora il valore di $ \displaystyle \sum_{i < j, i \mid j}{a_ia_j} $ incrementa (o resta uguale) se sostituiamo $ (a_x,a_y) $ con $ (a_x+a_y,0) $.
Ciò significa che possiamo ripetere il processo fin tanto che gli unici $ a_k $ che restano non nulli sono tutti e soli quelli che $ a_{k_1} \mid a_{k_2} $ e $ k_1<k_2 $. Bè adesso è conclusa con la disuguaglianza di MacLaurin, infatti è evidente che è sufficiente massimizzare il numero di elementi non nulli nel modo appena detto e si vede che abbiamo il massimo se quelli non nulli sono solo gli $ a_i $ tali che $ i $ è una potenza di 2. In questo modo infatti $ 2^8<300<2^9 $ per cui avremo al massimo 9 elementi (contando anche $ 1=2^0 $).
Il massimo si avrà quindi in $ \frac{4}{9} $ ponendo $ a_i=\frac{1}{9} $ se e solo se $ \text{gpf}(i)<3 $ (e si vede che tale massimo è effettivamente raggiungibile).

[Tibor Gallai]

Se $ (x,y) \in \mathbb{N}^2 $ t.c. $ 1\le x<y\le 300 $ e $ x \nmid y $ allora il valore di $ \displaystyle \sum_{i < j, i \mid j}{a_ia_j} $ incrementa (o resta uguale) se sostituiamo $ (a_x,a_y) $ con $ (a_x+a_y,0) $.

Se $ $a_2=a_4=\frac 12 $ e $ $(x,y)=(3,4) $, la sommatoria scende da $ $\frac 14 $ a $ $0 $.
O di nuovo non capisco quello che dici?
Sicuramente è mal formulato/formalizzato, quindi potrei aver frainteso completamente tutto il discorso.

EDIT: oki, si può mettere a posto.
Per ogni $ $i\in \{1,\ldots,300\} $ definiamo

$ $S_i:=\big\{j\in \mathbb{N}\ \big\mid (1\leq j \leq 300) \wedge (j\neq i) \wedge (j|i \vee i|j)\big\} $,

$ $s_i:=\sum_{j\in S_i}a_j $.

Prendiamo 2 indici $ $i\neq j $, tali che il minore non divida il maggiore, e tali che $ $s_i\geq s_j $. Poiché i 2 indici non "interagiscono" tra loro nella sommatoria finale, si può "trasferire" $ $a_j $ in $ $i $ (ponendo $ $a'_i:=a_i+a_j $ e $ $a'_j:=0 $), con garanzia di aumetare la somma finale di esattamente

$ $a_j(s_i-s_j) \geq 0 $.

Tutto il resto funziona (non preso alla lettera, ma si riesce a capire cosa vuol dire...).