3

This is kind of an algebra question, and I am interested in an algebric proof to it.

Suppose we have $k$ natural numbers that are all greater than $0$.

We would like to arrange them in multiplication-pairs of two, such that the sum of each pair's product is the lowest possible.

For example: Given $A = \{5,9,1,3,6,12\}$, a minimal product of pairs multiplication is taking the pairs $(1,12), (3,9), (5,6)$, such that $ 1 \cdot 12 + 3 \cdot 9 + 5 \cdot 6$ is the lowest possible.

Is it safe to say, that for each pair selection out of the set of the natural numbers, we pair the minimal with the maximal, then remove them from the set and go on?

TheNotMe
  • 4,841

4 Answers4

2

Yes. If we have pairs $(a,b)$ and $(c,d)$ such that $a = \max(a,b,c,d)$ and $c = \min(a,b,c,d)$, then $ac + bd < ab + cd$ so swapping $b$ and $c$ makes the sum decrease. By repeating these operations, we eventually end up in the state where the maximum and minimal numbers are paired et cetera.

You can also proceed inductively, showing that the maximal and minimal element should be paired and applying the inductive hypothesis on the remaining numbers.

user133281
  • 16,073
1

This is related to the subject of rearrangement inequalities.

Suppose that we have real numbers $x_1,x_2,\ldots,x_k$, without loss of generality assume that $x_1\le x_2\le\cdots\le x_k$. Let $y_1,y_2,\ldots,y_k$ be real numbers. If ${\bf z}=(z_1,z_2,\ldots,z_k)$ is a permutation of $y_1,y_2,\ldots,y_k$, define the sum $$S({\bf z})=\sum_{j=1}^k x_jz_j\ .$$ Then $S({\bf z})$ has its minimum value when $z_1\ge z_2\ge\cdots\ge z_k$, that is, when the $y_j$ are arranged in decreasing order.

David
  • 82,662
  • Thank you for pointing out the relevant subject. So, you're also saying that my theory is correct? having pairs of min * max at each step is optimal? – TheNotMe Mar 10 '14 at 21:12
  • Not $100$% sure but I think so. Taking both the $x_j$ and the $y_j$ to be your given numbers, the rearrangement inequality shows you how to get the minimum value of twice your sum, which will then also give you the minimum value of your sum. – David Mar 10 '14 at 21:18
1

?: A={1,2,3} Suppose you have made one pair (1,2) and removed it from the set. How do you make another pair?
Your reasoning requires additional conditions.

Saying set to be containing even number of elements would be better.

Sensebe
  • 915
1

Yes, your conjecture is correct. Suppose you have two integers in your first set $a,b$, and two integers in your second set $c,d$, where $a \leq b$ and $c \leq d$. Then $(a +d)(b+c) \geq (a+c)(b+d)$ which can be seen by substitution and noting that $A(A-B) = A^2 - AB \leq (A-\alpha B)(A+ (1 - \alpha) B) = A^2 - AB + \alpha(1 - \alpha)B^2$ for any $0 \leq \alpha \leq 1$. Then when you expand the inequality $(a +d)(b+c) \geq (a+c)(b+d)$ and rearrange you get $ac + bd \geq ad + bc$. This is all you need to prove your conjecture -- if two integers are out of reverse order in the sum of products representation, then you can swap the order and obtain a smaller sum of products.

user2566092
  • 26,142