Lowest product of pair multiplication 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?

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.
