Find the maximum of the $f=\sum_{i=1}^{n}\left(\binom{a_{i}}{2}\cdot\sum_{j<k,j,k\neq i}a_{j}a_{k}\right)$

Question

Let $a_{1},a_{2},\ldots,a_{n}$ be integers, such that $a_{i}\ge 0$ for $i=1,2,\cdots,n$, and such that $\sum_{i=1}^{n}a_{i}=120$. Find the maximum value of $$F=\sum_{i=1}^{n}\left(\binom{a_{i}}{2}\cdot\sum_{j<k,j,k\neq i}a_{j}a_{k}\right).$$

I tried the following: when $n\mid120$, taking all of the $a_i$ to be equal, then $$F=n\binom{120/n}{2}\binom{n-1}{2}\left(\dfrac{120}{n}\right)^2=\dfrac{120^3(120-n)(n-1)(n-2)}{4n^3}.$$ If $n\le 6$, then it's clear that $n=5$ gives the maximum value, which turns out to be $4769280$. But I can't prove this is actually the maximum value.

Answer 1

First off, $a_i\choose2$ is only well defined when $a_i\geq2$. So I will run with that assumption for the rest of this answer.

Suppose $2<a_1\leq a_2$. Let $F$ be defined as you've defined it, and let $F'$ be defined on $a_1-1, a_2+1,\ldots,a_n$ in the same way. We seek to show that $F'\leq F$. If we succeed, we've shown that to maximize $F$, all of the $a_i$ should be as close to equal as possible.

Now, we want to see the differences between $F$ and $F'$. Note that for $i>2$, the only differences in the term are in the inner summation, as $a_i\choose2$ doesn't change. In the inner summation, we note that for all $a_j$ where $j\neq1,2,i$, $(a_1-1)a_j+(a_2+1)a_j=a_1a_j+a_2a_j$. So, the only term that changes in the inner summation is $v_F=a_1a_2$ in $F$, and $v_{F'}=(a_1-1)(a_2+1)=a_1a_2-a_2+a_1-1$ in $F'$. Since $a_1\leq a_2$, $v_{F'}<v_F$. In particular, this means that for each term $j$ in the main summation that isn't $1$ or $2$, the $F'$ term is at least $a_j\choose2$ less than the $F$ term.

Now, we consider the terms $1$ and $2$. In the inner summation for $1$, note that in $F'$, we have $(a_2+1)\cdot a_j=a_2a_j+a_j$ for every $j\neq2$ while in $F$, we have $a_2a_j$ as the corresponding term. All other terms in the inner summation are clearly the same in both $F$ and $F'$.

So, for the first term, $F'$ is at most ${a_1\choose2}\cdot\sum\limits_{i=3}^n a_i$ greater than $F$ (Since $F$ multiplies the inner summation by $a_1\choose2$ and $F'$ multiplies it by $a_1-1\choose2$, the difference is actually less than this, but it doesn't matter here).

The corresponding analysis on term $2$ tells us that $F'$ is at least ${a_2\choose2}\cdot\sum\limits_{i=3}^n a_i$ less than $F$ in this term. As ${a_2\choose2}\geq{a_1\choose2}$, our proof is complete.