Maximum of Sums of Product Pairs

Question

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?

@RobertLewis I copied them from here: http://www.youtube.com/user/lastromanticx — גלעד ברקן, Mar 04 '14 at 02:04
@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 05 '14 at 17:04
@the_candyman I think Peter Košinár offers a very elegant proof. — גלעד ברקן, Mar 05 '14 at 22:20

score 3 · Accepted Answer · answered Mar 03 '14 at 21:50

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.

Maximum of Sums of Product Pairs

1 Answers1