Question

LetS=x₁y₁+x₂y₂+^...+x_nx_n, where x_1,x_2,...,x_n and y_1,y_2,...,y_n are orderings of two different sequences of positive real numbers, each containing n elements.

a) Show that S takes its maximum value overall orderings of the two sequences when both sequences are sorted (so that the elements in each sequence are in non-decreasing order).

b) Show that S takes its minimum value over all orderings of the two sequences when one sequence is sorted into non-decreasing order and the other is sorted into non-increasing order.

Short answer

a) The sequence y should be in non-decreasing order to maximize the addition.

b) The sequence y should be in non-increasing order to minimize the addition.

Step-by-step solution

Introduction

Increasing sequence means when in the sequence the next term is greater than the previous one. Similarly, decreasing sequence means when in the sequence the next term is smaller than the previous one.

Proof using generality for both cases

LetS=x₁y₁+x₂y₂+^...+x_nx_n, where x_1,x_2,...,x_n,and y_1,y_2,...,y_n are orderings of two different sequences of positive real values, each containing n elements.

Now explaining both the parts as follows:

a) Without the loss of generality, assume that the x sequence is already sorted into non-decreasing order, because we can re-label the indices.

There are only a finite number of possible orderings for the y sequence, so if we can show that increase the addition (or at least keep it the same) whenever we find y_iand y_jthat are out of order (that is i<j,but y_i>y_j) by switching them, then we will have shown that the addition is largest when the y sequence is in non-decreasing order.

Indeed, if perform the swap, then we have added x_iy_j+x_jy_ito the addition and subtract x_iy_i+ x_jy_j.

The net effect is to have added

x_iy_j+ x_jy_i- x_iy_{i -}x_jy_j= (x_j - x_i) (y_{i -}y_j)

This is non-negative by ordering assumptions. Therefore, the sequence y should be in non-decreasing order to maximize the addition.

b) Without the loss of generality, assume that the x sequence is already sorted into non-decreasing order, because we can re-label the indices.

There are only a finite number of possible orderings for the y sequence, so if we can show that decrease the addition (or at least keep it the same) whenever we find y_iand y_j that are out of order (that is i < j,but y_i<y_j) by switching them, then we will have shown that the addition is smallest when the y sequence is in non-increasing order.

Indeed, if perform the swap, then we have added x_iy_j+ x_jy_i to the addition and subtracted x_iy_i+ x_jy_j.

The net effect is to have added

x_iy_j+ x_jy_i- x_iy_{i -}x_jy_j= (x_j - x_i) (y_{i -}y_j)

This is non-negative by ordering assumptions. Therefore, the sequence y should be in non-increasing order to minimize the addition.