Maximize a sum. Let $m$ be a fixed positive integer.
Consider two sequences of non-negative integers $a_1, a_2, ..., a_m$ and $b_1, b_2, ..., b_m$ which both taken together add up to $n$, that is, $\sum a_i + \sum b_i = n$, where $n$ is fixed positive integer.
Then what is the maximum value that the sum $\sum a_ib_i$ can attain?
Intuitively it seems that the answer should be $ [\frac{n^2}{4}] $. I'm wondering how to prove it rigorously.
 A: Since $(a_i+a_j)(b_i+b_j)\ge a_ib_i+a_jb_j$, the sum never decreases when we replace $a_i$ by $a_i+a_j$, $b_i$ by $b_i+b_j$ and $a_j$ and $b_j$ by $0$. Thus we can assume $a_i=b_i=0$ for $i\ne1$, and then it's a simple one-dimensional optimization to show that $a_1b_1$ is maximal for $a_1=\lfloor n/2\rfloor$ and $b_1=\lceil n/2\rceil$, with maximal value $\lfloor n/2\rfloor\lceil n/2\rceil=\lfloor n^2/4\rfloor$.
A: Edit: The following answer does not take into account that the $a_i$, $b_i$ should be integers.
Your conjecture is correct. For a proof you can do without calculus:
Given the condition $a+b=C$ the product
$$ab={1\over 4}\bigl((a+b)^2-(a-b)^2\bigr)={1\over 4}\bigl(C^2-(a-b)^2\bigr)$$
is largest when $a=b$. Therefore we should choose $a_i=b_i$ $\ (1\leq i\leq m)$.
The problem now is to maximize $Q:=\sum_{i=1}^m a_i^2$ under the condition $\sum_{i=1}^m a_i={\displaystyle{n\over2}}$. 
When $a>0$, $a'>0$ then  $$a^2+a'^2 <(a+a')^2 + 0\ .$$ It follows that replacing any  pair $a_i>0$, $a_{i'}>0$ by the pair $a_i+a_{i'}$, $0$ will increase $Q$, so that $Q$ becomes maximal  when $a_1={n\over2}$ and all other $a_i=0$. Therefore  $Q_{\max}={n^2\over4}$ indeed.
