Maximum of $\sum_{i\neq j} n_in_j$ 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$?
 A: 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)
A: 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}
$$
