Let $n\geq 4;\ $ let $x_1,\ldots,x_n,\ y_1,\ldots,y_n\in \mathbb{R}:\ x_i,\ i=1,\ldots,n $ are not all equal.

Proposition: To find a permutation $\sigma(x_1),\ldots \sigma(x_n)\ $ of $x_1,\ldots,x_n\ $ which gives the least value of $\ y_1\sigma(x_1) + \ldots + y_n\sigma(x_n)$ greater than $x_1 y_1 + \ldots + x_n y_n$, we only need to swap the position of two values $x_i, x_j$ in $x_1, \ldots, x_n.$

It seems to be true based on experimentation, but I've no idea how to prove it. We may assume WLOG that $y_1<\ldots<y_n,$ but this isn't very impressive. What next?

Here is some Python code I wrote:

import itertools

num1 = [1,2,3,4]
num2 = [1,2,3,4]

print(sum([i*j for (i, j) in zip(num1, num2)]))

permutations = list(itertools.permutations(num1))

for i in permutations:


print(len(permutations_new), permutations_new)

for k in range(len(permutations_new)):
    print(sum([i*j for (i, j) in zip(permutations_new[k], num2)]))

1 Answer 1


The proposition is false.

Take $x_1,x_2,x_3 = 5,6,3$ and $y_1,y_2,y_3 = 1,2,4.$ Then $\displaystyle\sum_i x_i y_i = 29.$

The rearrangement $\{\sigma(x_i)\}$ which gives the least value of the sum greater than $29$ is $\sigma(x_1)=6,\ \sigma(x_2) = 3,\ \sigma(x_3) = 5,$ which gives $\displaystyle\sum_i y_i \sigma(x_i) = 32.$ You cannot get from $5,6,3$ to $6,3,5$ via swapping position of only two terms, and so the proposition is false.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .