2
$\begingroup$

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

$\endgroup$

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
4
  • $\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, 2019 at 12:01
  • $\begingroup$ (+1) This bound is right. I had miscomputed the best $\lambda$ in my answer. $\endgroup$
    – robjohn
    Mar 21, 2019 at 12:18
  • $\begingroup$ I have some trouble understanding the first statement of your solution... $\endgroup$
    – saisanjeev
    Mar 25, 2019 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, 2019 at 18:49
0
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2019 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$ Mar 25, 2019 at 15:27
  • $\begingroup$ Thanks! But in the solution why has he assigned arbitrary value for $y_{k+1}$? $\endgroup$
    – saisanjeev
    Mar 29, 2019 at 9:55
0
$\begingroup$

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

$\endgroup$
4
  • $\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, 2019 at 12:02
  • $\begingroup$ I have fixed where $\lambda$ is optimized. I get the same $\lambda=\frac12$ now. $\endgroup$
    – robjohn
    Mar 21, 2019 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, 2019 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, 2019 at 18:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .