Integers minimizing sum of square roots given a sum constraint

Let $n$, $m<n$, and $l<n$ be three integers. Minimize the following sum: $\sum_{i=1}^m \sqrt{n_i}$ such that $\sum_{i=1}^m n_i = n$, $n_i\leq l$ and $n_i\in \mathbb{N}$. Could we prove that $$ n_1=..=n_k=l,\;\; n_{k+1}=q,\;\;n_{k+2}=..=n_m=0$$ is the optimal solution, where $k$ and $q$ are given by the Euclidien division $n=k\;l+q$.

Solution 1:

First, show that if the list $(n_1, \dots ,n_m)$ has two entries $n_i$ and $n_j$ for which $$ \ell>n_i\ge n_j>0, $$ then the list is not minimal. Proving this intermediate inequality is helpful: $$ \sqrt{n_i+1}+\sqrt{n_j-1}< \sqrt n_i +\sqrt{n_j}. $$ This shows that the list obtained by replacing $n_i$ with $n_i+1$ and $n_j$ with $n_j-1$ has a smaller sum of square roots. Therefore, an optimal list can have at most one entry which is neither $0$ nor $\ell$. Let us call this entry $q$. If we let $k$ be the number of occurrences of $\ell$, we have $n=k\ell+q$, as required.