I have the following question with me:

The numbers $x_1, x_2, . . . , x_n$ obey $−1 \leq x_1, x_2, . . . , x_n \leq 1$ and $$x_1^3 + x_2^3 + ... + x_n^3 = 0 $$ Prove that $$x_1 + x_2 + · · · + x_n ≤ \frac{n}{3}$$

They provide the following solution:

Substitute $y_i = x_i^3$ so that $y_1 + ... + y_n = 0$ and we want to maximize $y_1^{1/3} + y_2^{1/3} + ... + y_n^{1/3}$ we observe the concavity/convexity of the function $f(y) = y^{1/3}$ and hence we may put $$y_1=...=y_k=-1$$

From here I could not follow the solution. How can we just put the above numbers? How does it help in the solution?

Source of question and solution : https://robertkosova.files.wordpress.com/2018/09/olympiad-inequalities-thomas-mildorf-2006.pdf Question number 15 solution 1


With this function that's neither concave nor convex, we want to push the values apart in some places and together in others. We're pushing them apart for negative $x$, and $-1$ is as far as we can go in that case.

Now, what I would do with this one? Start with that same substitution $y_i=x_i^3$. We wish to maximize $\sum_i y_i^{1/3}$ given $\sum_i y_i = 0$ and $-1\le y_i\le 1$.

To do so, we will find a linear (affine) function $g$ so that $y^{1/3}\ge g(y)$ for all $y\in[-1,1]$, and $g$ is as large as possible. This $g$ will touch the graph of $y^{1/3}$ twice, crossing at $-1$ and being tangent to it at some positive $c$. Now, $g(y)-y^{1/3}=ay-y^{1/3}+b$ is a cubic polynomial in $y^{1/3}$. We know it has a root at $y=-1$ and a double root at $y=c$, so we can write down its factored form: $$ay-y^{1/3}+b = g(y) = a(y^{1/3}+1)(y^{1/3}-c^{1/3})^2 = a\left(y+(1-2c^{1/3})y^{2/3}+\cdots\right)$$ Equating the $y^{2/3}$ coefficients, $1-2c^{1/3}=0$ and $c=\frac18$. The line between $(-1,-1)$ and $(\frac18,\frac12)$ has slope $\frac{3/2}{9/8} = \frac43$, so $g(y)=\frac43y+\frac13$.

All right, now we have that $\frac43y + \frac13 \ge y^{1/3}$ for all $y\in [-1,1]$. Apply this to each $y_i$ and take the sum: $$\sum_{i=1}^n y_i^{1/3} \le \sum_{i=1}^n \left(\frac43y_i+\frac13\right) = \frac43\left(\sum_{i=1}^ny_i\right) +\frac n3 = \frac n3$$ And that's it. Equality occurs when each $y_i$ is equal to either $-1$ or $\frac18$, which is possible if $n$ is divisible by $9$; for other $n$, there's a slightly stronger bound that's difficult to calculate exactly.

I'm pretty sure I've seen this problem before. Looking back - that substitution didn't really make much difference. I'm pretty sure I didn't use it the first time I dealt with this one.

  • $\begingroup$ I've corrected the equality case - but it's still something that happens for infinitely many $n$. Your claimed bound can't possibly be uniformly true. $\endgroup$ – jmerry Mar 21 at 12:01
  • $\begingroup$ (+1) This bound is right. I had miscomputed the best $\lambda$ in my answer. $\endgroup$ – robjohn Mar 21 at 12:18
  • $\begingroup$ I have some trouble understanding the first statement of your solution... $\endgroup$ – saisanjeev Mar 25 at 14:06
  • $\begingroup$ It's not critical to anything else; that first statement is a heuristic for why the maximum should occur in the place it does, and is not used directly in the material that follows. If we're trying to maximize $\sum_i f(x_i)$ for fixed $\sum x_i$ and a concave function $f$, Jensen's inequality means that the $x_i$ should all be as close together as possible. If $f$ is convex instead, the opposite of Jensen's inequality means that the $x_i$ should be as far apart as possible. For a function that mixes convexity and concavity, we get a mix of the two behaviors instead. $\endgroup$ – jmerry Mar 25 at 18:49

Suppose we have a set of values of $y_1,\ldots,y_n$ summing to $0$ which maximise $\sqrt[3]{y_1}+\cdots +\sqrt[3]{y_n}$.

Suppose $-1<y_i<y_j\leq 1$. If $y_i+y_j<0$ then subtracting a small amount from $y_i$ and adding it to $y_j$ increases the sum of cube roots, contradiction. If $y_i+y_j>0$ then we can subtract from $y_j$ and add to $y_i$, increasing the sum of cube roots, again a contradiction. Finally, if $y_i+y_j=0$ we can replace them both by $0$ without changing the sum of cube roots - then there must be a new pair $y_i<y_k$ with sum $>0$, which we deal with as above.

Thus to maximise the sum of cube roots we must have some number $k$ of $-1$ terms and all others equal. The order doesn't matter, so we may assume the first $k$ are $-1$ and the rest equal - clearly this means each of the others is $\frac{k}{n-k}$. Now we just need to check which value of $k$ works best.

  • $\begingroup$ can you please explain that step where you subtract a small amount from one of them and add it to the other... $\endgroup$ – saisanjeev Mar 25 at 14:18
  • 1
    $\begingroup$ @saisanjeev if you change $x$ by a small value $\delta$, then $\sqrt[3]{x}$ changes by about $\delta$ times the derivative, i.e. $\frac13x^{-2/3}\delta$ (for $x\neq 0$). This is a bigger change the closer $x$ gets to $0$. So if you add a small amount to whichever of $y_i,y_j$ is closer to zero, and subtract it from the other one, the addition makes a bigger difference to $\sqrt[3]{y_i}+\sqrt[3]{y_j}$ than the subtraction, so the total increases. $\endgroup$ – Especially Lime Mar 25 at 15:27
  • $\begingroup$ Thanks! But in the solution why has he assigned arbitrary value for $y_{k+1}$? $\endgroup$ – saisanjeev Mar 29 at 9:55

We want $$ \sum_{k=1}^n\delta x_k=0\tag1 $$ for all $\delta x_k$ so that $$ \sum_{k=1}^nx_k^2\,\delta x_k=0\tag2 $$ On the edge, $x_k^2=1$, and in the interior, orthogonality requires $x_k^2=\lambda^2$, for some $0\le\lambda\lt1$.

Let $k$ be the sum of the signs of the $x_k^2=1$ and $m$ be the sum of the signs of the $x_k^2=\lambda^2$. Then given $$ k+m\lambda^3=0\tag3 $$ we want to maximize $$ k+m\lambda=m\!\left(\lambda-\lambda^3\right)\tag4 $$ From which, we can see that $m\ge0$ and $k\le0$. We also have $j=m-k\le n$.

From $(3)$, we have $k=-j\frac{\lambda^3}{1+\lambda^3}$ and $m=j\frac1{1+\lambda^3}$. Thus, the maximum of $(4)$ is $$ \sum_{k=1}^nx_k=k+m\lambda\le\frac{\lambda-\lambda^3}{1+\lambda^3}\,j\le\frac13\,n\tag5 $$ where the maximum $\frac{\lambda-\lambda^3}{1+\lambda^3}=\frac13$ is attained at $\lambda=\frac12$.

  • $\begingroup$ A counterexample to your claimed inequality: $n=1$, $x_1=-1$, $x_2=x_3=\cdots=x_9=\frac12$. The sum of the $x_n$ in that case is exactly $3=\frac n3$. $\endgroup$ – jmerry Mar 21 at 12:02
  • $\begingroup$ I have fixed where $\lambda$ is optimized. I get the same $\lambda=\frac12$ now. $\endgroup$ – robjohn Mar 21 at 12:20
  • $\begingroup$ $\frac{\lambda-\lambda^3}{1+\lambda^3}=\frac13-\frac{4(2\lambda-1)^2}{3(2\lambda-1)^2+9}$ $\endgroup$ – robjohn Mar 21 at 12:50
  • $\begingroup$ For a given $n$, choose $m\approx\frac{8n}9$ and $k\approx-\frac{n}9$ and set $\lambda=\left(-\frac km\right)^{1/3}$. $\endgroup$ – robjohn Mar 21 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.