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?

  • 1
    $\begingroup$ How do you get those beautiful Hebrew letters? $\endgroup$ – Robert Lewis Mar 3 '14 at 20:45
  • $\begingroup$ @RobertLewis I copied them from here: youtube.com/user/lastromanticx $\endgroup$ – גלעד ברקן Mar 4 '14 at 2:04
  • $\begingroup$ @גלעדברקן what's wrong with my answer? $\endgroup$ – the_candyman Mar 4 '14 at 17:52
  • 1
    $\begingroup$ @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. $\endgroup$ – גלעד ברקן Mar 5 '14 at 17:04
  • $\begingroup$ he gives you just an intuition... I give a rigorous proof! $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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