All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Sum of squares (Posted on 2012-01-28)
For the non-negative numbers a, b, c and d, such that:
a<=1, a+b<=5, a+b+c<=14, a+b+c+d<=30: Prove that sqrt(a)+sqrt(b)+sqrt(c)+sqrt(d)<=10

 No Solution Yet Submitted by Ady TZIDON No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 Proving the lemma Comment 2 of 2 |
In my last post, I asserted that
Lemma:  If n non-negative terms sum up to k, then the sum of their square roots is maximized if each term = k/n.

This can be proved without calculus.

Consider two non-negative terms that sum up to 2a.
They can be represented as (a-x) and (a+x).

What value of x maximizes sqrt(a-x) + sqrt(a+x)?
When squared, this equals 2a + sqrt(a^2 - x^2), and that is clearly maximized when x = 0.  So, the sum of the square roots of two unequal positive terms can always be made greater by replacing each term with the average of the two.

And because we can always do pair-wise operations on a set of n terms, that means that the sum of the square roots of n unequal positive terms can always be improved by replacing those terms by their collective average.

For instance, consider 4 terms which sum to 16:
1, 2, 4, 9
Replace the smallest and the largest with their pairwise average, giving 5,2,4,5
Do it again, giving 3.5, 3.5, 4, 5
Do it again, giving 4.25, 3.5, 4, 4.25
Do it again, giving 3.875, 3.875, 4, 4.25
At each stage the sum of the square roots increases, and the process will converge on  4,4,4,4, which maximizes the sum of the square roots of positive numbers that sum to 16.

 Posted by Steve Herman on 2012-01-30 21:26:32

 Search: Search body:
Forums (0)