Proof for two sequences producing the maximum value when sorted 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.
 A: 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$.
A: 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.
A: 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.
A: 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$
