Maximize multivariable function ( from Brazilian mathematical olympiad)

Question

Let $n$ be a positive integer bigger than one. Find the maximum value of:

$x_1^3 + x_2^3 + \ldots + x_n^3$

given that $x_1 + x_2 + \ldots + x_n = 0$ and $x_1^2 + x_2^2 + \ldots + x_n^2 = 1$.

This is what I have tried:

Analyzing both conditions separately it is possible to conclude that such value is greater than $0$ and smaller than $1$. Using Newton's identities we have:

$P_3 = e_1\ P_2 - e_2\ P_1 + 3 e_3 = 3 e_3$ (since $e_1 = P_1 = 0$) and $1 = P_2 = -e_2/2 \geq e_2 = -1/2$.

If we take the partial derivative of $S$ with respect to $x_i$, we get: $3 (e_2 - x_i(e_1 - x_i)) = 3 ((x_i)^2 - 1/2)$.

The real problem is that I don't know how to use all this information to solve the problem.

Answer 1

The curved surfaces are various values for your function, the red sphere is the second constraint, and the orange plane the first constraint:

Can you see the symmetry that allows you to make this a one-dimensional problem (and hence trivial)?

Your solution lies on a (hyper) circle.

And thus....

Answer 2

Let us consider the problem for $n = 3$. One can show that for the optimal solution, we have WLOG $x_1 = x_2 < x_3$ (exercise) when $x$ maximises $x_1^3 + x_2^3 + x_3^2$. As mentioned in David G. Stork's answer, the domain over which you're maximising in this case is a circle, so it's trivial to solve the problem using 1D maximisation techniques.

Now for the $n$-dimensional case. WLOG, suppose $x_1 \leq x_2 \leq x_3$ with at least 2 of these values distinct. Then define $k = \frac{x_1 + x_2 + x_3}{3}$. Then let $j^2 = (x_1 - k)^2 + (x_2 - k)^2 + (x_3 - k)^2$, $j$ positive. Then we see that picking $y_i = \frac{x_i - k}{j}$, the $y_i$ must maximise $y_1^3 + y_2^3 + y_3^2$ under the constraints that $y_1 + y_2 + y_3 = 0$ and $y_1^2 + y_2^3 + y_3^2 = 1$. This shows that it must be the case that $x_1 = x_2 < x_3$.

So this means that $n$ can only take on two different values, $a$ and $b$, since if we took on three different values, we would have WLOG $x_1 < x_2 < x_3$. And we must have at least two different values, for if we only had one value, it would need to be zero, but that contradicts $\sum x_i^2 = 1$.

WLOG, suppose $a < b$. We can only have a single occurence of $b$ in $x$. For if we had 2 or more, then WLOG take $x_1 = a$ and $x_2 = x_3 = b$. Then $x_1 < x_2 = x_3$. Then $x_1 = x_2$; contradiction.

So we must have $n - 1$ occurences of $a$ and $n$ occurences of $b$. This gives us the following: $(n - 1)a + b = 0$. Then $b = -(n - 1) a$. Then $(n - 1) a^2 + b^2 = (n - 1)a^2 + (-(n - 1)a)^2 = n(n - 1) a^2 = 1$. Then $a = \pm \sqrt{\frac{1}{n(n - 1)}}$, and $b = \mp \sqrt{\frac{n - 1}{n}}$. Clearly, we must have $a$ negative and $b$ positive. This gives us our maximising quantity of $(n - 1) (-\sqrt{\frac{1}{n(n - 1)}})^3 + (\sqrt{\frac{n - 1}{n}})^3$.