Puzzle question:

For the non-negative numbers a, b, c and d,

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

Answer:

A good way to solve this puzzle is to make a substitution.  If we define new variables represented by capital A,  B, C, and D as follows, then the solution is easier:

Let A=sqrt(a)-1
Let B=sqrt(b)-2
Let C=sqrt(c)-3
Let D=sqrt(d)-4

Now, solving for a, b, c, and d, we get the following equations.

a = A^2 + 2A + 1
b = B^2 + 4B + 4
c = C^2 + 6C + 9
d = D^2 + 8D + 16

Since a <= 1, and a+b <= 5, etc., we get the following four inequalities:

a = A^2 + 2A + 1 <= 1
a+b = A^2 + B^2 + 2A + 4B + 5 <= 5
a+b+c = A^2 + B^2 + C^2 + 2A + 4B + 6C + 14 <= 14
a+b+c+d = A^2 + B^2 + C^2 + D^2 + 2A + 4B + 6C + 8D + 30 <= 30

Notice that in each inequality the same constant appears on both sides, so they cancel:

A^2 + 2A <= 0
A^2 + B^2 + 2A + 4B <= 0
A^2 + B^2 + C^2 + 2A + 4B + 6C <= 0
A^2 + B^2 + C^2 + D^2 + 2A + 4B + 6C + 8D <= 0

A square is always non-negative, so it can be subtracted from the "less than" side of an equality:

2A <= 0
2A + 4B <= 0
2A + 4B + 6C <= 0
2A + 4B + 6C + 8D <= 0

Now multiply the first inequality by 6, the second by 2, the third by 1, and the fourth by 3:

6 (2A) <= 0
2 (2A + 4B) <= 0
1 (2A + 4B + 6C) <= 0
3 (2A + 4B + 6C + 8D) <= 0

Now add up the four equations, then divide by 24:

24A + 24B + 24C + 24D <= 0

A + B + C + D <= 0

Now substitute the lower-case expressions in place of A, B, C, and D, and then add 10 to both sides:

sqrt(a)-1+sqrt(b)-2+sqrt(c)-3+sqrt(d)-4 <= 0

sqrt(a)+sqrt(b)+sqrt(c)+sqrt(d) <= 10

That's it!  Pretty easy, don't you think?

Nick Hobson's Proof

Hi Graeme,

I thought you might be interested in another proof of this inequality, which uses Jensen's inequality 

f(x) = sqrt(x) is concave on non-negative reals.

Taking n = 4,
weights 1/10, 2/10, 3/10, 4/10, and
x(i) = a, b/4, c/9, d/16, we obtain

(1/10)*sqrt(a) + (2/10)*sqrt(b/4) + (3/10)*sqrt(c/9) + (4/10)*sqrt(d/16) <= sqrt(a/10 + b/20 + c/30 + d/40).

Hence

sqrt(a) + sqrt(b) + sqrt(c) + sqrt(d) <= 10*sqrt((12a + 6b + 4c + 3d)/120).

But

12a + 6b + 4c + 3d = 3(a + b + c + d) + (a + b + c) + 2(a + b) + 6a <= 3*30 + 14 + 2*5 + 6*1 = 120.

The result follows.

Regards,
Nick

Related pages in this website

Jensen's inequality can be used to solve the "sum of sqrts" puzzle.

The webmaster and author of the Math Help site is Graeme McRae.
     [home]  [email]  [search]  [Links to Math Sites]  [Whiteboard]