# 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.

-
oh yes, thanks, I will remove it. –  dineshdileep Nov 27 '12 at 9:42

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 really good one –  dineshdileep Nov 27 '12 at 10:03

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.

-
What if $n$ is odd? –  N N Nov 27 '12 at 9:56