0
$\begingroup$

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))
permutations_new=[]

for i in permutations:
    permutations_new.append(list(i))

print(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)]))
$\endgroup$
0

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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