Call 2 of the numbers $ a_i$ and $ a_j$ friendly if either $ i|j$ or $ j|i$ (with $ i \ne j$). Similarly, we call 2 numbers $ a_i, a_j$ unfriendly if they are not friendly, and $ i \ne j$. Now, if we take any 2 unfriendly numbers $ a_i, a_j$ each with non-zero values, we can increase the sum by either replacing $ (a_i,a_j)$ with $ (a_i + a_j,0)$ or $ (0,a_i + a_j)$. We repeat the process until it eventually halts. Then all of the non-zero numbers must be friendly towards each other, else we could apply the process one more time. Now, if $ A$ is the set of the $ i$ such that $ a_i$ s non-zero, then we now have $ \sum_{i \in A} a_i = 1$ and we need to maximize $ \sum_{i,j \in A, i < j}a_ia_j$. But this is less than $ (|A| choose 2/|A|^2)(\sum_{i \in A} a_i)^2 = (|A| choose 2/|A|^2) = \frac {1}{2}(1 - \frac {1}{|A|})$. So we need to maximize the size of $ |A|$. Clearly this is can be no larger than when $ A = {1,2,4,8,16,32,64,128,256}$, which gives $ A$ 9 elements. Hence the max. is $ \frac {1}{2}(1 - \frac {1}{9}) = \frac {4}{9}$. We can attain equality when $ a_1 = a_2 = a_4 = a_8 = a_{16} = a_{32} = a_{64} = a_{128} = a_{256} = \frac {1}{9}$ and the rest of the $ a_i = 0$.

rofler wrote: Now, if we take any 2 unfriendly numbers $ a_i, a_j$ each with non-zero values, we can increase the sum by either replacing $ (a_i,a_j)$ with $ (a_i + a_j,0)$ or $ (0,a_i + a_j)$. I really don't understand this step. Could you explain it again for me?

We are replacing the 2 numbers with one of those 2 pairs. One of them will increase the number, this is easy to see (I could write out the proof, but it is only one or 2 lines).

actually,for a number which contains a prime divisor greater than $3$,we can porve by adjustment that it must be zer0.

Well, we could just take that all two integers $ i,j $ from $ 2^n $ to $ 2^{n+1}-1 $ has "$ i $ doesn't divide $ j $". So, just $ \sum_{i \neq j, i|j} a_ia_j \leq \prod_{i=0}^{8}(a_{2^i}+...+a_{2^{i+1}-1}) \leq \frac{4}{9}$. (Well, actually it's the same idea as above. )

See also Korean 2015

smy2012 wrote: See also Korean 2015 Yeah, I took that exam (It was really funny to see same problem appearing from an old exam. ) And actually, it's Final 2013. https://www.artofproblemsolving.com/community/c6h526260p2983427

toto1234567890 wrote: smy2012 wrote: See also Korean 2015 Yeah, I took that exam (It was really funny to see same problem appearing from an old exam. ) And actually, it's Final 2013. https://www.artofproblemsolving.com/community/c6h526260p2983427 It's very old actually. In my knowledge, it first appear in here

The key observation is that if $i$ and $j$ do not divide each other, and $a_i$ and $a_j$ are both nonzero, then replacing either $(a_i, a_j)$ with $(a_i+a_j, 0)$, $(0, a_i+a_j)$ will not decrease the sum, but will increase the number of zero terms. So apply this operation until it's no longer possible. Let $I = \{ i : a_i \neq 0 \}$. If $I = \{ i_1 < \dots < i_k \}$ we have $i_1 \mid \dots \mid i_k$. Now the sum in question (by Cauchy or anything else) is at most $\frac{1}{2}(1-k^{-1})$. So we want to maximize $k$, which occurs at $k=9$. This gives the upper bound $4/9$. Equality occurs of course at $a_1 = a_2 = a_4 = \dots = a_{256} = 1/9$.

Really nice smoothing problem. Notice that for any $i, j$ that don't divide each other, the expression is linear in $a_i$ and $a_j$, thus the smoothing $(a_i, a_j) \to (a_i+a_j, 0)$ or to $(0, a_i+a_j)$ will increase the sum. In particular, repeating this operation a maximal number of times, we are left with some number of $k \leq 9$ terms, all of which divide each other. The upper bound can easily be seen to be $\frac 49$ now by Cauchy.

Our answer is $\boxed{\frac 49}$, attained with $a_i=\tfrac 19$ if $i=2^j$ and $a_i=0$ otherwise. Consider two indices $m$, $n$ such that $m \nmid n$, $n \nmid m$. The change in the desired expression by switching $(a_m,a_n) \rightarrow (a_m+a_n,0)$ has opposite sign as the change in $(a_m,a_n) \rightarrow (0,a_m+a_n)$, so we can always (weakly) increase our sum using this algorithm. Further, note $\sum a_i$ remains invariant at 1. Our algorithm terminates when all nonzero terms have indices which are multiples/divisors of each other, meaning there can be at most 9 nonzero terms (the powers of 2). If the remaining numbers are $b_i, \ldots, b_k$, our expression is \[\sum b_ib_j = \frac 12 \left(\left(\sum b_i\right)^2 - \sum b_i^2\right) \leq \frac 12 \left(1 - \frac 1k\right) \leq \boxed{\frac 49}. \quad \blacksquare\]