Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
oh yes, thanks, I will remove it. –  dineshdileep Nov 27 '12 at 9:42

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
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.

share|improve this answer
    
What if $n$ is odd? –  N N Nov 27 '12 at 9:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.