Let $\{n_i\}_{i=1}^k$ be $k$ natural number so that $\sum_{i=1}^k n_i=n$. Then what is the maximum of $\sum_\limits{i\neq j} n_in_j$?


Because $$ \begin{align} \sum_{i\ne j}n_in_j &=\left(\sum_{i=1}^kn_i\right)^2-\sum_{i=1}^kn_i^2\\ &=n^2-\sum_{i=1}^kn_i^2 \end{align} $$ So maximizing $\sum\limits_{i\ne j}n_in_j$ is equivalent to minimizing $\sum\limits_{i=1}^kn_i^2$.

By Hölder's Inequality, $$ \begin{align} k\sum_{i=1}^kn_i^2 &=\sum_{i=1}^k1^2\sum_{i=1}^kn_i^2\\ &\ge\left(\sum_{i=1}^kn_i\right)^2\\[9pt] &=n^2 \end{align} $$ and we can realize this minimum by letting $n_i=\frac nk$.

However, $n_i$ are supposed to be integers, so we need to make a small adjustment. Although we may not be able to set $n_i=\frac nk$ since this might not be an integer, we must have that $|n_i-n_j|\le1$. Suppose not, and that for some $i,j$, we have that $n_i-n_j\gt1$. Then $$ n_i-n_j-1\gt0 $$ and therefore $$ \begin{align} (n_i-1)^2+(n_j+1)^2 &=n_i^2+n_j^2-2(n_i-n_j-1)\\ &\lt n_i^2+n_j^2 \end{align} $$ which means that $n_i$ and $n_j$ are not part of a minimal arrangement. Thus, we must have $|n_i-n_j|\le1$. This implies that $n-k\left\lfloor\frac nk\right\rfloor$ of the $n_i$ must equal $\left\lfloor\frac nk\right\rfloor+1$ and the rest must equal $\left\lfloor\frac nk\right\rfloor$.

Thus, with this minimal arrangement for the sum of the squares, we get $$ \begin{align} \sum_{i\ne j}n_in_j &=n^2-\sum_{i=1}^kn_i^2\\ &\le n^2-k\left\lfloor\frac nk\right\rfloor^2-\left(n-k\left\lfloor\frac nk\right\rfloor\right)\left(2\left\lfloor\frac nk\right\rfloor+1\right)\\ \end{align} $$

  • $\begingroup$ How are you sure that $n_i=n/k$ is a natural number? $\endgroup$ – A.Γ. Oct 17 '17 at 17:11
  • $\begingroup$ @A.Γ.: That should be handled now. $\endgroup$ – robjohn Oct 18 '17 at 10:00

You can rework the expression: $$ \sum_{i\neq j} n_i n_j = \sum_i n_i \sum_j n_i - \sum_i n_i^2 = n^2 - \sum_i n_i^2,$$ so the problem can be addressed by minimizing $\sum_i n_i^2$ under the same constraint.

Clearly, for the optimal solution $$\max_{i,j} |n_i - n_j| \leq 1.$$ Indeed, if it weren't the case, the value of the sum could be decreased by moving a unit from the greatest $n_i$ to the lowest. Clearly, one of the optimal solutions is such that the $l$ first numbers are be equal to $a+1$ and the rest are equal to $a$. Then $$ \sum_i n_i = l (a+1) + (k-l) a = ka + l.$$ The optimal values are $a = n/k$ (integer division), $l = n\%k$ (remainder of the integer division). So the minimal value of $\sum_i n_i^2$ is equal to $$(n\%k)(n/k+1)^2 + (k-n\%k)(n/k)^2$$ and $$ \min \sum_{i\neq j}n_i n_j = n^2 - (n\%k)(n/k+1)^2 - (k-n\%k)(n/k)^2.$$ Note that when $n\%k = 0$, one recovers the solution that I had found previously in the unconstrained case, i.e. $$n^2 - n^2/k$$ (see the edit history of this post for details)

  • $\begingroup$ Why do you think that $n_i=n/k$ is a natural number? $\endgroup$ – A.Γ. Oct 16 '17 at 16:17
  • $\begingroup$ woops, I had skipped the work "natural"... $\endgroup$ – Roberto Rastapopoulos Oct 16 '17 at 16:18
  • $\begingroup$ Should be fixed now. :) $\endgroup$ – Roberto Rastapopoulos Oct 16 '17 at 16:38

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.