Maximize sum of paired products without replacement from {1,…,2n}Given {1,…,2n}, how do you pair off the elements such that: when you multiply within each of the n pairs, the resulting products have maximal sum?Here is an example: For n = 2, this would mean pairing off elements of {1,2,3,4}, taking the product within each pair, and then adding all of those products up: where the goal is to maximize the resulting sum.In this example, you could use: { 1 , 2 } , { 3 , 4 } → 1 ⋅ 2 + 3 ⋅ 4 = 2 + 12 = 14 { 1 , 3 } , { 2 , 4 } → 1 ⋅ 3 + 2 ⋅ 4 = 3 + 8 = 11 { 1 , 4 } , { 2 , 3 } → 1 ⋅ 4 + 2 ⋅ 3 = 4 + 6 = 10Since the pairwise product sums in this case are 14,11, and 10, we find that the maximum is 14. In particular, the maximum occurs when we pair off consecutive numbers. I suspect that the consecutive pairing may always be optimal (and that pairing first with last, second with second to last, etc may always result in the minimal pairwise product sum).I'm not sure how to prove (or disprove!) this, and would appreciate a proof or a pointer to one. I suspect this problem has already been considered, so I include a ref-req tag as there may be terminology unfamiliar to me. If there are generalizations of this problem (e.g., starting with a set other than the first consecutive 2n positive integers) then related references will be most welcome, too!

Question

Maximize sum of paired products without replacement from {1,…,2n}Given {1,…,2n}, how do you pair off the elements such that: when you multiply within each of the n pairs, the resulting products have maximal sum?Here is an example: For   n  =  2, this would mean pairing off elements of {1,2,3,4}, taking the product within each pair, and then adding all of those products up: where the goal is to maximize the resulting sum.In this example, you could use:  {  1  ,  2  }  ,  {  3  ,  4  }  →  1  ⋅  2  +  3  ⋅  4  =  2  +  12  =  14  {  1  ,  3  }  ,  {  2  ,  4  }  →  1  ⋅  3  +  2  ⋅  4  =  3  +  8  =  11  {  1  ,  4  }  ,  {  2  ,  3  }  →  1  ⋅  4  +  2  ⋅  3  =  4  +  6  =  10Since the pairwise product sums in this case are 14,11, and 10, we find that the maximum is 14. In particular, the maximum occurs when we pair off consecutive numbers. I suspect that the consecutive pairing may always be optimal (and that pairing first with last, second with second to last, etc may always result in the minimal pairwise product sum).I&#039;m not sure how to prove (or disprove!) this, and would appreciate a proof or a pointer to one. I suspect this problem has already been considered, so I include a ref-req tag as there may be terminology unfamiliar to me. If there are generalizations of this problem (e.g., starting with a set other than the first consecutive 2n positive integers) then related references will be most welcome, too!

hamputlnf · Accepted Answer

Step 1Let’s take four positive numbers, say a,b,c and d, such that   a  ≤  b  ≤  c  ≤  d. Then:  (  d  −  a  )  (  b  −  c  )  ≤  0  ⇔  a  c  +  b  d  ≤  a  b  +  c  d  (  d  −  b  )  (  a  −  c  )  ≤  0  ⇔  a  d  +  b  c  ≤  a  b  +  c  dThat means when you consider a set of 4 positive numbers, pairing them in the ascending order will give you the maximum sum.Step 2Now, consider any set of 2n positive numbers, and pair them randomly. You can now apply the following process:1. Find two pairs such that the numbers are not paired in the ascending order.2. Switch the numbers in these two pairs so you get the ascending order. The new pairing now gives an higher sum, because we only changed the 4 numbers involved in these pairs.3. Repeat until you can’t.This process will end when your pairs are made with your numbers in the ascending order; hence, it maximizes your sum!