# Maximum of Sums of Product Pairs

Given two ascending distinct integer sets, $A = A(0), A(1), \dots, A(n)$, and $B = B(0), B(1), \dots, B(n)$, I'm looking for the maximum sum, where elements from $B$ are multiplied by elements from $A$, for example:

\begin{align} \max \{ & A(0)B(0) + A(1)B(1) + \dots, \\ & A(0) B(1) + A(1) B(0) + \dots, \\ & \dots \} \end{align}

My instinct says that the maximum sum will always be the largest elements from $B$ multiplied by the largest elements from $A$. That is,

$$\max = A(n)B(n) + A(n-1)B(n-1) + \dots$$

Is this correct and can it be shown/proven?

• How do you get those beautiful Hebrew letters? – Robert Lewis Mar 3 '14 at 20:45
• @RobertLewis I copied them from here: youtube.com/user/lastromanticx – גלעד ברקן Mar 4 '14 at 2:04
• @גלעדברקן what's wrong with my answer? – the_candyman Mar 4 '14 at 17:52
• @the_candyman I'm not sure why you think something may be wrong with your answer. I chose to accept and up-vote Peter Košinár's answer because it was easy/easier for me to follow. – גלעד ברקן Mar 5 '14 at 17:04
• he gives you just an intuition... I give a rigorous proof! – the_candyman Mar 5 '14 at 21:57

Your intuition is correct. Imagine that, instead of having $A_n$ paired up with $B_n$, we had $A_n$ combined with some smaller $B_j$ and $B_n$ combined with some smaller $A_i$. What would happen if we changed the pairings into $A_nB_n + A_iB_j$? This can be answered by the following inequality: $$(A_n - A_i)(B_n - B_j)>0$$ which, after expanding and moving two terms to the other side yields $$A_n B_n + A_iB_j > A_n B_j + A_iB_n$$ In other words, if the biggest terms are not paired to each other, the sum is not as big as it can be.