# 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)$

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

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.

• A bit algebra shows $F=-\frac{1}{4} \left(\sum _{i=1}^n a(i)^2\right){}^2+\sum _{i=1}^n \left(\frac{a(i)^4}{2}-\frac{121 a(i)^3}{2}+3690 a(i)^2\right)-432000$. It's probably not easy to describe when this takes maiximum for fixed $n$. Dec 10, 2019 at 11:53
• @ablmf Wait, unless there's a typo, $4768524\color{red}<4769280$. Dec 10, 2019 at 13:50

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. 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'}. 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.

• $\binom{a_i}2$ is well defined for any $a_i$, in any unital ring where $2$ has an inverse. It is simply $\frac{a_i(a_i - 1)}2$. Dec 9, 2019 at 22:07
• @WhatsUp Interesting, but I don't think it changes my answer. Dec 9, 2019 at 22:09
• Sure... just pointing that out (: Dec 9, 2019 at 22:10