Guliash's blog

How to prove?
By Guliash, 11 years ago, In English

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:)

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
11 years ago, # |
← Rev. 5   Vote: I like it +6 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's called the rearrangement inequality. Now that you know its name, I believe you can google it for more information?

→ Reply