Please help me with the following problem: $$\text{minimize }\sum\limits_{i=1}^{t}{{{m}_{i}}.\left( \frac{{{m}_{i}}-1}{2} \right)},$$ subjected to: $$\sum\limits_{i=1}^{t}{{{m}_{i}}=n-1},$$ and $$t<\frac{n}{2},$$ where ${{m}_{i}}$ and $t$ are natural numbers.
Thank you .
Use the quadratic-mean inequality:
\begin{eqnarray*}E:=\sum\limits_{i=1}^t{m_i\left( \frac{m_i-1}{2} \right)} &=& {1\over 2}\sum\limits_{i=1}^t(m^2_i-m_i)\\ &\geq &{1\over 2t}\Big(\sum\limits_{i=1}^tm_i\Big)^2-{1\over 2}\sum\limits_{i=1}^tm_i \\ &=& {1\over 2t}(n-1)^2-{1\over 2}(n-1)\\ &>& {1\over n}(n-1)^2-{1\over 2}(n-1)\\ &=& {(n-1)(n-2)\over 2n} \end{eqnarray*}
Well, we can be a little more accurate:
If $n$ is even, then $t$ is at most ${n\over 2}-1$ so $E_{\min} ={n(n-1)\over 2(n-2)}$ and this is achieved when $m_1=m_2=...=m_t = {n-1\over t} = {2n-2\over n-2}$.
Similarly analysis goes if $n$ is odd. Then $t$ is at most $n-1 \over 2$ so $E_{\min} ={n-1\over 2}$ and this is achieved when $m_1=m_2=...=m_t = 2$.
