Doubt in the solution provided to an inequality question

Question

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

Answer 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.

Answer 2

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.

Answer 3

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$.