Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

4 Answers 4

up vote 2 down vote accepted

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.

share|improve this answer
    
Yes I guess induction is the way. Thank you so much. –  TheNotMe Mar 10 at 21:01

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.

share|improve this answer
    
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 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 at 21:18

?: 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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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