Proof for two sequences producing the maximum value when sorted

Question

I am trying to improve my discrete Math skills by doing some proof exercises. But I am struggling to understand how to start proving the following hypothesis:

$$ S = {x}_1{y}_1 + {x}_2{y}_2 + \ldots + {x}_n{y}_n $$ Where ${x}_1,{x}_2\ldots{x}_n$ and ${y}_1,{y}_2\ldots{y}_n $ are ordering of two different sequences of positive real numbers, each containing n elements. S takes its maximum value when ${x}_1,{x}_2\ldots{x}_n$ and ${y}_1,{y}_2\ldots{y}_n $ are sorted in non decreasing order.

I was thinking that I should maybe use a proof by contradiction. Where the negation of the hypothesis is: S takes it minimum value over all ordering of the two sequences when both sequences are sorted into non increasing order.

However I am not sure my negation of the hypothesis is correct or how proceed from there. I do not want the complete proof because I am trying to learn how to do it myself but if some one can tell me how to make a start on this I would be grateful.

Answer 1

Hint: consider a pair of indices $i < j$, so that $x_i \le x_j$ and $y_i \le y_j$. Now, study the difference between the expression $S$, when they are sorted, and the analogous expression $S'$, when one pair is out of order: $$ S - S' = (x_i y_i + x_j y_j) - (x_i y_j + x_j y_i) $$ Try to factor this expression to show that the difference $S - S'>0$.

Answer 2

The negation of the statement is: the value of $x_1 y_1 + \cdots x_n y_n$ is NOT maximum when $x$ and $y$ are sorted. This is the same as: there exist a different ordering of $x$ and $y$ such that $x_1 y_1 + \cdots x_n y_n$ is greater that the same expression with $x$ and $y$ ordered.

Answer 3

First, you need to determine what the hypothesis is and what the conclusion is.

To proceed with a proof by contradiction, you ASSUME the hypothesis and NEGATE the conclusion. Then argue to reach a contradiction.

If the implication you are trying to prove is as follows:

"if ("when") $x_1,x_2, …, xn$ and $y_1, y_2, …y_n\;$ are sorted in non decreasing order, then $S$ takes a maximal value"

then the conclusion is "$S$ takes a maximal value."

The negation of the conclusion is "$S$ does not take a maximal value". There exists some other, greater $S' > S$ such that S is not maximal.

Then you affirm the hypothesis, state the negation of the conclusion, and show that a contradiction result.

Answer 4

Using the hint by Sammy Black.

Proof: Assume that $i<j, x_i<x_j$ and $y_i<y_j, S$ as the sum of which both x and y sequence are sorted, and without loss of generality, $S'$ is the sum in which x is sorted and y is not in nondecreasing order. Thus subtracting $S'$ from $S$, we get:

$$ S - S' = x_iy_i +x_iy_i - x_iy_j - x_jy_i$$

Factoring $y_i-y_j$ give us: $$ S - S' = (y_i - y_j)(x_i - x_j)$$

Because $y_i<y_j \implies y_i-y_j<0$ and $x_i<x_j \implies x_i-x_j<0$ we can conclude that: $$(y_i - y_j)(x_i - x_j)=S-S'>0$$ $$S>S'$$ $\therefore$ The sum in which x and y are sorted is the maximum value. $\blacksquare$