I came across this equation in a programming contest(I have simplified it a lot):
So the problem directly is we are given some constants < $a_1$ , $a_2$ .. . . . $a_n$ >
and we need to decide the order of <$x_1$ , $x_2$ ...... , $x_n$ >
such that $\sum_1^n a_k * x_k$ (where k varies from 1 to n ) is maximum .
Note we are given both the sets < $a_1$ , $a_2$ .. . . . $a_n$ > and
So, I have a strong intuition that for the summation to be of maximum value - we should sort both the co efficients in non decreasing order and take the summation of $a_i * x_i$ .
Let the sorted lists be denoted by same set(just for convenience) i.e.
< $a_1$ , $a_2$ .. . . . $a_n$ > and <$x_1$ , $x_2$ ...... , $x_n$ >
Now to prove this I was trying to use Induction .
Induction Hypothesis : Let there be i elements in two sets such that their summation of products is maximum when they are sorted in non decreasing order.
Base Case: Tried to prove for < $a_1$ , $a_2$ > and < $x_1$, $x_2$ > and suceeded easily!(Tried all cases assuming $x_1$>$x_2$ and $a_1$>$a_2$ . )
Now , Let the hypothesis be true till n-1
Now , to prove that my hypothesis is true what I was trying is trying to prove:
$a_1$ * $x_1$ + $a_2$ *$x_2$ + . . . . + $a_n-1$ * $x_n-1$ + $a_n$* $x_n$ >= $a_1*x_1$ + . . . . . . + $a_k$ *$x_n$ + . . . . $a_n$ * $x_k$
where < $a_1$ , $a_2$ .. . . . $a_n$ > and are non decreasing
I proved this right but I feel like this is kind of an incomplete proof because I am assuming only two coefficients i.e. $x_n$ and $x_k$ only will be swapped , but more than 2 coefficients can be swapped!
Trying to prove a more general form , I couldn't succeed! Can you help in proving this via Induction ? I can be wrong at earlier steps too . But I don't think I am!