1
$\begingroup$

Someone, please, make that title more readable. My lack of math English does not let me.


Given $A = a_1 + ... + a_k;\ A, a_i > 0$ what is $\max\left(\sum_{i<j}a_i a_j\right)$?

An obvious upper bound is $\dfrac{A^2}{2}$, because $\sum_{i<j}a_i a_j = \dfrac{A^2 - \sum_i a_i^2}{2}$.

Something tells me the maximum is when $\forall i\ a_i = \dfrac{A}{k}$, but I cannot prove it properly.

$\endgroup$
1
$\begingroup$

Hint: formulate this as a constraint maximization problem and apply Lagrange Multipliers. The $a_i$ are the input and they’re subject to the constraint that $\sum a_i=A$.

$\endgroup$
1
$\begingroup$

Since you already have the intuition that they all has to be equal to each other, I will argue why this is true.

You already noted that \begin{equation} 2\sum_{i<j}a_ia_j= A^2 - \sum_{i}^{k}a_i^2 \end{equation} hence equivalently we are trying to minimize $\sum a_i^2$. Now suppose we have a minimal solution where there exists $a_i,a_j$ such that $a_i\neq a_j$. Without loss of generality, say $a_1>a_2$.

Let $a=\frac{a_1+a_2}{2}$. Compare $(a_1,a_2,a_3,\dots, a_k)$ and $(a,a, a_3, \dots, a_k)$. Since $a_3^2+a_4^2 +\dots + a_k^2$ part is equal: \begin{equation} \begin{aligned} a_1^2+a_2^2 > a^2 + a^2&\iff a_1^2 + a_2^2 > \frac{(a_1+a_2)^2}{2} \\&\iff a_1^2 + a_2^2 > 2a_1a_2\\ &\iff (a_1-a_2)^2 > 0 \end{aligned} \end{equation} which is true and contradicts that we started with a minimal solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.