Sorry for the weird name of topic.
We have two arrays of non-negative integers A and B. Their length is N
Let's sort these arrays.
A' — a permutation of A.
How to prove that there is no A' such that:
A'[1]*B[1]+..+A'[N]*B[N] > A[1]*B[1]+...+A[N]*B[N]. (A and B are sorted)
I understand that it is a clear fact but I can't prove it.
Sorry for my English. I tried to write correctly:)
Proof.
If A' is unordered, there are two elements A'[i] > A'[i+1]. It is easy to show, that
A'[i] * B[i] + A'[i+1] * B[i+1] <= A'[i] * B[i+1] + A'[i] * B[i+1]
So we can swap elements A[i] and A[i+1] and the value of A'[1]*B[1]+..+A'[N]*B[N] will be the same or greater
We can repeat the process while A' is unordered
Hence, the greatest value of A'[1]*B[1]+..+A'[N]*B[N] is achieved when A' is non-decreasing
Elements of A and B can be negative.
Let A1 < A2 < ... An, and let i < j: A'i > A'j. Then we can swap A'i and A'j and sum A'1·B1 + ... + A'n·Bn will increase. Then we will swap such pairs while its exist. And when there isn't such pair, array is sorted. Therefore, initial sum A'1·B1 + ... + A'n·Bn less then sum A1·B1 + ... + An·Bn.
А зачем писать на английском?
В качестве упражнения. Так сказать, хоть какая-то, но практика.
Вот это неравенство в википедии
It's called the rearrangement inequality. Now that you know its name, I believe you can google it for more information?