# Fall 2016, problem 26

### Comments

Sorry, but my proof is perfectly valid. I used the substituion Z = X + 1. Go through my proof step by step. If I have an email I can send my writing. Regards, H. Zimmermann

I had a third solution based on splitting the x's into negative and nonnegative sets and using the convexity of x^3 but it is not worth detailing here because HRZ solution is simply brilliant !

The main reason we do not see more elegant solutions like the solution of HRZ is that the potential contributors are bound to enter LaTeX by hand. Is there a way to post a PDF or TIFF or a link to them ?

I apologize humbly to HRZ, who I wronged in an earlier comment in a lapse of judgement. Finally some welcome activity on the board and I decide it's my time for being discouraging. Honest mistake, I swear. I claim the opposite, of what I said and agree that your solution - contrary to mine - is indeed brilliant.

@rubs: While composing your post, you can insert an image file conveniently via a button right above the text draft. Right next to it there is a button for inserting html links. Just upload you PDF to your favorite free file hosting service and link it. I too would like to see more solutions - be they elegant or not - or discussions.

The quadratic has a minimum value of 3/4 at its vertex. It follows that the expressun is aleays larger then ∑ni=13zi4.

I apologize for the lengthiness of this proof. I'm probably making this seem harder than it actually is.

The basic idea behind it all is that the set $$S:=\{(x_1, ..., x_n) \in \mathbb{R}^n : \sum {x_i}^3 = 0 \textrm{ and } \forall i : x_i >= 1\}$$ is a compact subset of $\mathbb{R}^n$ and so $\sum x_i$ assumes a maximum on $S$, which we try to find in an explicit form as much as possible. What makes this approach kind of technical is that $S$ is not a smooth manifold, in which case you could maybe hope to find the maximum by a more straightforward variational calculation.

Anyway, here's the

**Proof:**
If possible, pick $i$ and $j$, such that none of the numbers $x_i$ and $x_j$ is equal to -1 or 0.
Define
$$\begin{eqnarray*}
s &:=& {x_i}^3 + {x_j}^3 \\
S &:=& x_i + x_j \\
x_i' &>=& 1 \textrm{ arbitrary} \\
x_j' &:=& (s - {x_i'}^3)^{\frac{1}{3}} \\
S' &:=& x_i' + x_j'
\end{eqnarray*}$$

Then we have: $$ {x_i'}^3 + {x_j'}^3 = {x_i}^3 + {x_j}^3 = s$$

Here's how $S'$ changes, as we vary $x_i'$: $$\frac{dS'}{dx_i'} = \frac{d}{d x_i'} (x_i' + x_j') = 1 + \frac{dx_j'}{d x_i'} = 1 - \frac{{x_i'}^2}{{x_j'}^2}$$ Note that $\frac{dS'}{dx_i'} >= 0$ if $|x_i'| \leq |x_j'|$.

That means, that if we start with $x_i' = x_i$ and $x_j' = x_j$, we may increase the one with the smaller absolute value continuously without changing $s'$, without violating the restriction $x_i'$, $x_j' >= -1$ and without making $S'$ any smaller until one of two things happens:

- One of $x_i'$ and $x_j'$ becomes 0 or -1
- $|x_i'|$ becomes equal to $|x_j'|$

Since $S' >= S$ it always suffices to prove the estimate $\sum x_i \leq \frac{n}{3}$ for the tuple of numbers $(x_k)$ with $x_i$ and $x_j$ replaced by $x_i'$ and $x_j'$.

Using the arguments above you can reduce the problem to the case where the first $l$ numbers in the tuple $(x_k)$ are either equal to 0 or -1 and the remaining $(n -l)$ numbers all have the same absolute value. Moreover you can discard the $x_k$ that are equal to zero (say there are $z$ of them), since they they don't contribute to either $\sum x_i^3$ or $\sum x_i$ and $\sum_{i=1}^n x_i \leq \frac{n-z}{3}$ is an even better estimate then required.

Our situation has become considerably simpler now:

- There are $a$ numbers equal to -1.
- There are $b \neq 0$ numbers equal to $u > 0$.
- There are $c = n - a - b$ numbers equal to $-u$.

The case $b = c$ can be excluded as trivial, since it would mean, that $\sum x_i = 0$. Therefore: $$ 0 = -a + b u^3 - c u^3 \implies u = \left (\frac{a}{b - c} \right )^{\frac{1}{3}}$$

So $$\sum_{i=1}^n x_i = -a + b u - c u = -a + (b - c)^{\frac{2}{3}} a^{\frac{1}{3}}$$

When you hold $a$ fixed, this expresion becomes largest for $b = n-a$ and $c=0$: $$\sum_{i=1}^n x_i \leq -a + (n - a)^{\frac{2}{3}} a^{\frac{1}{3}} = n \left (-\alpha + (1 - \alpha)^{\frac{2}{3}} \alpha^{\frac{1}{3}} \right )$$

Here we have defined $\alpha := \frac{a}{n}$, so $0 \leq \alpha \leq 1$. It is standard to show, that the function $f$ defined by $$\begin{eqnarray*} &&f: [0, 1] \to \mathbb{R} \\ &&\alpha \mapsto -\alpha + (1 - \alpha)^{\frac{2}{3}} \alpha^{\frac{1}{3}} \end{eqnarray*}$$ assumes a maximum of $\frac{1}{3}$ at $\alpha = \frac{1}{9}$. This concludes the proof.

Hans' proof is elegant! I came at the problem in a slightly different way, but the proof is essentially the same as Hans'.

Start with $\sum_{i=1}^n(x_i - \frac{1}{2})^2 (x_i+1) \ge 0$ since both $(x_i - \frac{1}{2})^2$ and $(x_i+1)$ are never negative.

This expands to $\sum_{i=1}^n(-\frac{3}{4}x_i+\frac{1}{4}) \ge 0$ where the identity $\sum_{i=1}^nx_i^3=0$ has been used.

Then do the sum over $\frac{1}{4}$ and rearrange to get $ \sum_{i=1}^nx_i \le \frac{n}{3}$

Hello, I am a german mathematical physicist m.sc, ph.d Cambridge University. Hans R. Zimmermann

My solution is very simple. :

substitute $z_i = x_i + 1$

The summation reads now as: $\sum_{i=1}^n ( z_i^3 - 3z_i^2 + 3z_i - 1 ) = 0$

So we have a polynomial of degree 3 and $\sum_{i=1}^n$ stands for summation from 1 to n . We now bring the -1 in the bracket to the right side and factor $z_i$ in the polynomial expression on the left. This leaves us with

$\sum_{i=1}^n (z_i(z_i^2 -3z_i + 3))= n$

We observe that a quadratic in z appears which is factored by z. The quadratic has a minimum value of 3/4 at its vertex. It follows that the expressun is aleays larger then $\sum_{i=1}^n \frac{3z_i}{4}$. Substituting again $z_i$ by $x_i+1$ leads to the unequality which we had to prove.

$\sum_{i=1}^n x_i \le \frac{n}{3}$

I enjoy to contribute in honor of your founder.

EDIT: Moderator added in latex to make the answer easier to read.