Inequality question­

$$a,b,c,d\ge 0$$ $$a\le 1$$ $$a+b\le 5$$ $$a+b+c\le 14$$ $$a+b+c+d\le 30$$

Prove that $\sqrt{a}+\sqrt{b}+\sqrt{c}+\sqrt{d}\le 10$.

We can subtract inequalities to get the answer, but that is wrong... I can't think of any another method... Any hints or suggestions will be helpful.

• It is like some maximization problem with given constraints, if it can help. – pointer Jul 19 '14 at 17:09
• I can't understand why subtracting inequalities is wrong?it works well! – Mahdi Jul 19 '14 at 17:17
• Put $a=0.5, b=4.5.$ – pointer Jul 19 '14 at 17:18
• It might make calculations easier to relabel the variables so that, for example $w^2+x^2\leq5$ and you want to maximize $w+x+y+z$. – Empy2 Jul 19 '14 at 17:20
• See the book "Putnam and Beyond", exercise 135 – AsdrubalBeltran Jul 19 '14 at 18:25

The function $f(a,b,c,d)=\sqrt{a}+\sqrt{b}+\sqrt{c}+\sqrt{d}$ has no stationary points inside the polyhedral domain (since the partial derivatives cannot vanish due to the concavity of the square root function), hence its maximum is attained on the boundary. By iterating the same argument on the boundary of the domain, we have that the maximum is achieved in a vertex of the polyhedron, and by checking them all we have that $$\operatorname{argmax}(\sqrt{a}+\sqrt{b}+\sqrt{c}+\sqrt{d})=(1,4,9,16),$$ from which $$\sqrt{a}+\sqrt{b}+\sqrt{c}+\sqrt{d}\leq 1+2+3+4 = 10$$ follows.

Let $(a_0,b_0,c_0,d_0)$ be a point in the domain where $\sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d}$ is maximized. It suffices to show that $a_0 = 1$, $a_0 + b_0 = 5$, $a_0 + b_0 + c_0 = 14$, and $a_0 + b_0 + c_0 + d_0 = 30$ for then you can solve for all four variables to get $(a_0,b_0,c_0,d_0) = (1,4,9,16)$.

We start with the last equation and proceed backwards. Note that if $a_0 + b_0 + c_0 + d_0$ were strictly less than $30$ we could increase $d_0$ slightly keeping the other variables fixed, and we'd stay in the domain yet $\sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d}$ would increase, contradicting maximality of $\sqrt{a_0} + \sqrt{b_0} + \sqrt{c_0} + \sqrt{d_0}$. So we must have $a_0 + b_0 + c_0 + d_0 = 30$. Note that since $a_0 + b_0 + c_0 \leq 14$ this means $d_0 \geq 16$. In particular $d_0 > c_0$ since $c_0 \leq 14$.

Moving to the equation $a_0 + b_0 + c_0 \leq 14$, if strict inequality held here then one could replace $c_0$ by $c_0 + \epsilon$ and $d_0$ by $d_0 - \epsilon$ for some small $\epsilon$ and we would stay in the domain. However we must have $\sqrt{c_0 + \epsilon} + \sqrt{d_0 - \epsilon} > \sqrt{c_0} + \sqrt{d_0}$. To see why, squaring this inequality we see it's equivalent to $$c_0 + d_0 + 2\sqrt{(c_0 + \epsilon)(d_0 - \epsilon)} > c_0 + d_0 + 2\sqrt{c_0d_0}$$ Subtracting $c_0 + d_0$ from both sides and squaring the result, we see this is the same as $$(c_0 + \epsilon)(d_0 - \epsilon) > c_0d_0$$ Equivalently, $$(d_0 - c_0)\epsilon - \epsilon^2 > 0$$ Since $d_0 \geq 16 > 14 \geq c_0$, this will hold if $\epsilon$ is small enough.

In summary, if we had $a_0 + b_0 + c_0 < 14$, then adjusting $c_0$ and $d_0$ as above would result in a new point $(a,b,c,d)$ in the domain for which $\sqrt{c} + \sqrt{d}$ is strictly larger than $\sqrt{c_0} + \sqrt{d_0}$. Since $a = a_0$ and $b = b_0$ are unchanged, $\sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d}$ is larger than $\sqrt{a_0} + \sqrt{b_0} + \sqrt{c_0} + \sqrt{d_0}$, contradicting the maximality of $\sqrt{a_0} + \sqrt{b_0} + \sqrt{c_0} + \sqrt{d_0}$.

We conclude $a_0 + b_0 + c_0 = 14$. To get the other two inequalities, you just iterate the above procedure to get $a_0 + b_0 = 5$, and then $a_0 = 1$.

Using AM-QM and the assumptions we get \begin{align*} \sqrt a + \sqrt b + \sqrt c + \sqrt d & = \sqrt a + 2\sqrt{\frac b4} + 3\sqrt{\frac c9} + 4 \sqrt{\frac d{16}} \\ & \le 10 \sqrt{\frac{a+2\cdot \frac b4 + 3 \cdot \frac c9 + 4 \cdot \frac d{16}}{10}} \\ & = \sqrt{10a+5b+\frac{10}3 c + \frac 52 d} \\ & = \sqrt{5a+\frac 53 (a+b) + \frac 56 (a+b+c) + \frac 52(a+b+c+d)} \\ & \le \sqrt{5 \cdot 1 + \frac 53 \cdot 5 + \frac 56 \cdot 14 + \frac 52 \cdot 30}\\ & = 10. \end{align*}

$d$ should be maximized, so the last inequality becomes an equation.

Keep $a,b$ fixed, and vary $c$ and $d=30-a-b-c$, perhaps $c$ must be maximized so the third inequality becomes an equation.

a<=1 ,a+b<=5 Or, b<=4 a+b<=5 , a+b+c<=14 c<=9 a+b+c<=24 ,a+b+c+d<=30 d<=16 sqrt a +sqrt b +sqrt c+sqrt d<=sqrt 1+sqrt 4+sqrt 9+sqrt 16 sqrt a+sqrt b+sqrt c+sqrt d <=10

• Take $a = 0$, $b = 5$, don't $a\le1$ and $a+b\le5$ hold? – Robert Badea Jul 19 '14 at 17:31
• You are correct...........@ robert badea... – rajai 7 Jul 19 '14 at 17:32
• @rajai7 Reading your answer makes me dizzy. Would you mind using MathJax? – Toby Mak Oct 20 '18 at 13:30

Solution:

Rewrite the expression as

$$\sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d} = \frac{1}{2}\sqrt{4a} + \frac{1}{\sqrt{2}}\sqrt{2b} + \frac{\sqrt{3}}{2}\sqrt{\frac{4}{3}c} + \sqrt{d}$$

Then apply the Cauchy-Schwarz inequality:

$$\left(\frac{1}{2}\sqrt{4a} + \frac{1}{\sqrt{2}}\sqrt{2b} + \frac{\sqrt{3}}{2}\sqrt{\frac{4}{3}c} + \sqrt{d}\right)^2 \leq \left(\frac{1}{4} + \frac{1}{2} + \frac{3}{4} + 1\right)\left(4a + 2b + \frac{4}{3}c+d\right) = \frac{10}{4}\left(\frac{12a + 6b + 4c+ 3d}{3}\right) = \frac{10}{12}(6a+ 2(a+b)+(a+b+c)+ 3(a+b+c+d)) \leq \frac{10}{12}(6+2\cdot 5 + 14 + 3\cdot30)= \frac{10}{12}\cdot 120 = 100$$

$$\implies \sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d} \leq 10$$

Explaning the magical solution:

This sounds as a magical solution and you may ask "How have I thought in the right coefficients?".Well, here the answer gets a little messy, but my idea was to use Cauchy-Schwarz inequality once and some suitable changes of variables, until be clear which coefficients I should choose. Let be $$\alpha,\beta, \gamma>0$$, then

$$E =(\sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d})^2 = \left(\frac{1}{\alpha}\sqrt{\alpha^2 a} + \frac{1}{\beta}\sqrt{\beta^2b} + \frac{1}{\gamma}\sqrt{\gamma^2c} + \sqrt{d}\right)^2$$

$$\leq \left(\frac{1}{\alpha^2}+ \frac{1}{\beta^2} + \frac{1}{\gamma^2}+ 1\right)(\alpha^2a+ \beta^2b + \gamma^2c + d ) \label{1}\tag{1}$$

where in the last inequality we used the Cauchy-Schwarz inequality. The idea now is use the facts that $$a\leq 1$$, $$a + b\leq 5$$, $$a + b + c\leq 14$$ and $$a + b + c + d\leq 30$$ considering a clever change of variables. So, let's define $$x,y,z \geq 0$$ such that

$$\gamma^2 = z+1$$

$$\beta^2 = y + \gamma^2 = y + z +1$$

$$\alpha^2 = x + \beta^2 = x +y + z + 1$$

Then, considering the second term in \ref{1}:

$$\alpha^2a+ \beta^2b + \gamma^2c + d = (x+ y + z +1)a + (y+ z +1)b + (z+1) c + d$$

$$= ax + (a+b)y + (a+b+c)z + a+b+c+d \leq x + 5y + 14z + 30$$

However, it would be better to let all as function of $$\alpha, \beta$$ and $$\gamma$$. We have

$$x + 5y + 14z+ 30 = \alpha^2 - \beta^2 + 5\beta^2 - 5\gamma^2 + 14\gamma^2 - 14 + 30$$

$$= \alpha^2 + 4\beta^2 + 9\gamma^2 + 16$$

Thus,

$$E \leq \left(\frac{1}{\alpha^2}+ \frac{1}{\beta^2} + \frac{1}{\gamma^2}+ 1\right)(\alpha^2 + 4\beta^2 + 9\gamma^2 + 16) \label{2}\tag{2}$$

Notice that $$\alpha,\beta,\gamma$$ are positive arbitrary numbers. So we just need to find $$\alpha,\beta,\gamma$$ such that \ref{2} is less or equal to 100. I tried some values and was unsuccessful. Then, I had the idea to let \ref{2} as symmetric as possible. Firstly, I rewrote it as

$$\left(\frac{1}{\alpha^2}+ \frac{1}{\beta^2} + \frac{1}{\gamma^2}+ 1\right)(\alpha^2 + 4\beta^2 + 9\gamma^2 + 16) = \left(\frac{4}{\alpha^2}+ \frac{4}{\beta^2} + \frac{4}{\gamma^2}+ 4\right)\left( \left(\frac{\alpha}{2}\right)^2 + 4\left(\frac{\beta}{2}\right)^2 + 9\left(\frac{\gamma}{2}\right)^2 + 4\right)$$

Let be $$s_0 = \frac{\alpha}{2}$$, $$w_0 = \frac{\beta}{2}$$ and $$t_0 = \frac{\gamma}{2}$$. So we get,

$$E \leq \left(\frac{1}{s_0^2}+ \frac{1}{w_0^2} + \frac{1}{t_0^2}+ 4\right)(s_0^2 + 4w_0^2 + 9t_0^2 + 4)$$

But we still can make better. Let be $$s_0= s$$, $$w_0 = w/\sqrt{2}$$ and $$t_0 = t/\sqrt{3}$$. Then,

$$E \leq \left(\frac{1}{s^2}+ \frac{2}{w^2} + \frac{3}{t^2}+ 4\right)(s^2 + 2w^2 + 3t^2 + 4)$$

One can easily see that $$s= w = t=1$$ provides

$$E \leq 100$$

Then, we show that

$$\sqrt{a} + \sqrt{b} + \sqrt{c} + \sqrt{d} = \sqrt{E} \leq 10$$

Notice that we need to check that this choice of variables is consistent with the suppositions on $$x,y,z$$, that is, that they are non-negatives. If we substitute to find the values of $$\alpha, \beta$$ and $$\gamma$$, we will find exactly the very same values of the coefficients proposed for the "magical solution".