Find the maximum of $\sum\limits_{i=1}^{n}(x^3_{i}-x_{i}x_{i+1}x_{i+2})$ subject to $0 \le x_i \le i, \forall i$

Question

let $n$ is give postive integer numers,and $x_{i},i=1,2,\cdots,n$ be real numbers,and such $$0\le x_{i}\le i,i=1,2,\cdots,n$$ Find the maximum of the value $$x^3_{1}+x^3_{2}+x^3_{3}+\cdots+x^3_{n}-(x_{1}x_{2}x_{3}+x_{2}x_{3}x_{4}+x_{3}x_{4}x_{5}+\cdots+x_{n-1}x_{n}x_{1}+x_{n}x_{1}x_{2})$$

I think this problem can't use Lagrange multiplier,because this is $n$ variable,so we must use Adjustment method?

ago,I post the three variable inequality,and It's not this problem special case,so this is different problem.I try it use Adjustment method and at last I failure it.

Answer 1

I will only cover the case $n \ge 6$. I will also adopt the convention that for every variable with subscript, the subscript is aliased modulus $n$. ie. $a_{n+1} = a_1, b_{n+2} = b_2, c_{0} = c_{n}, d_{-1} = d_{n-1}$.

Consider the problem of maximizing following expression

$$F(x_1,x_2,\ldots,x_n) = \sum_{k,cyc} (x_k^3 - x_k x_{k+1} x_{k+2})\tag{*1}$$

as $(x_1, x_2, \ldots, x_n)$ varies over the domain $D = [0,1] \times [0,2] \times \cdots \times [0,n]$.

Since $D$ is compact and $\Delta(\cdot)$ is continuous over $D$, $\Delta(\cdot)$ reaches its maximum at some point $(p_1,p_2,\ldots,p_n) \in D$. For each integer $k : 1 \le k \le n$, consider the function $\phi_k$ defined by

$$[0,k] \ni t \quad\mapsto\quad \phi_k(t) = F(p_1,\ldots,p_{k-1}, t, p_{k+1}, \ldots, p_n ) \in \mathbb{R}$$

It is clear $\phi_k(t)$ has the form

$$t^3 - t(p_{k-1}p_{k-2} + p_{k-1}p_{k+1} + p_{k+1}p_{k+2}) + \text{ terms independent of } t.$$ Since $\;\frac{d^2}{dt^2}\!\phi_k(t) = 6 t > 0\;$ over $(0,k]$, $\phi_k(t)$ is a strictly convex function there. This means $\phi_k(t)$ cannot reaches maximum at the interior of $[0,k]$. As a consequence,

$$p_k = k \;\text{ or }\; 0 \quad\text{ for }\quad k = 1,2,\ldots,n$$

This means in general, if we want to search for a maximum of $(*1)$, we only need to look at the $2^n$ vertices of its domain $D$.

We can actually do better than that.

Consider the differences of $\phi_k(t)$ at $t = 0$ and $t = k$:

$$\Delta_k = \phi_k(k) - \phi_k(0) = k\left[ k^2 - (p_{k-2}p_{k-1} + p_{k-1}p_{k+1} + p_{k+1}p_{k+2}) \right]\tag{*2}$$ By definition of $p_k$, $t = p_k$ is a maximum of $\phi_k(t)$. This implies

$$\Delta_k \begin{cases} \ge 0, & p_k = k\\ \le 0, & p_k = 0\end{cases}$$

if we look at the explicit form of $\Delta_k$ in $(*2)$, we can make several observations:

1. For any $k : k \le n-2$, if $p_{k+1}, p_{k+2} \ne 0$, then $$\Delta_k \le k (k^2 - p_{k+1}p_{k+1}) = k(k^2 - (k+1)(k+2)) < 0 \quad\implies\quad p_k = 0$$

2. For any $k : 3 \le k \le n-1$, if $p_{k+1} = 0$, then $$\Delta_k = k(k^2 - p_{k-2}p_{k-1}) = k(k^2 - (k-2)(k-1)) > 0 \quad\implies\quad p_k = k$$

3. Bases on observations $1$ and $2$, we find for any $k : 4 \le k \le n-2$, if $p_{k+2} = 0$, then $p_{k+1} = k+1$ and one and only one of $p_{k}, p_{k-1}$ vanishes.

   To see which one should vanish, we can compare the values of $$\begin{align} & F(\ldots,p_{k-2},0,k,p_{k+1},\ldots) - F(\ldots,p_{k-2},0,0,p_{k+1},\ldots)\\ \text{ vs. }\quad & F(\ldots,p_{k-2},k-1,0,p_{k+1},\ldots) - F(\ldots,p_{k-2},0,0,p_{k+1},\ldots) \end{align}$$ The corresponding values are $$k^3 \quad\text{ vs. }\quad (k-1)((k-1)^2 - p_{k-3}p_{k-2})$$ Since RHS > LHS, we can conclude it is $p_{k-1}$ that vanishes.

4. Notice $$\Delta_n \ge n (n^2 - ((n-2)(n-1) + (n-1) + 2)) = n(2n-3) > 0$$ we have $p_n = n$. By observation 1. and 2. again, we find one and only one of $p_{n-1}$, $p_{n-2}$ vanishes. By a similar analysis as step $3$ above, one find that it is $p_{n-2}$ that vanishes.

Combine all these observations, we can conclude aside from some exceptions at the low end (i.e $k < 4$ ), the zeros of $p_k$ start at $k = n - 2$ at the high end and repeat at regular interval of $3$ towards the lower end. This significantly cut down the possible choices of $p_k$ from $2^n$ to a very small number.

There are still some loose ends. In particular, what are the exact places where $p_k = 0$ at the low end? I'm not going to spend more time to sort out these last details. Let's just say for the special case $n = 25$ that inspire this question, the maximum is occurred at

$$(p_1,\ldots,p_{25}) = ( 0, 0, 3, 4, 0, 6, 7, 0, 9, 10, 0,12,13, 0,15,16, 0,18,19, 0,21,22, 0,24,25)$$

with value $75824$. For this particular case, we see the zeros of $p_k$ clearly follows the pattern of repeat at regular interval of $3$ except at the low end. At $k = 1$ and $2$, this pattern breaks with a pair of repeated zeroes.

Answer 2

Remarks: For the case that $n = 3k, k \in \mathbb{N}_{\ge 2}$, here is a solution without using calculus. My solution is inspired by achille hui's nice answer. Perhaps this idea can be extended to the other cases.

Case $n = 3k, k \in \mathbb{N}_{\ge 2}$

Let $$F := x_1^3 + x_2^3 + \cdots + x_n^3 - (x_1x_2x_3 + x_2 x_3 x_4 + \cdots + x_{n-1}x_nx_1 + x_nx_1x_2).$$

The maximum of $F$ is given by $\frac{27}{2}k^4 + 18k^3 + \frac92k^2 - k$ when $x_{3i+1} = 0, x_{3i+2} = 3i+2, x_{3i+3} = 3i+3$ for $i = 0, 1, \cdots, k-1$.

Proof.

First, we give the following auxiliary result.

Fact 1: Let $p\ge 1$ be fixed. Let $a\in [0, p]$ and $b\in [0, p+1]$ and $c \in [0, p+2]$. Then the maximum of $a^3 + b^3 + c^3 - abc$ is $(p+1)^3 + (p+2)^3$ when $a = 0, b = p+ 1, c = p + 2$.
(The proof is given at the end.)

Using Fact 1, we have \begin{align*} F &\le \sum_{i=0}^{k-1} \left(x_{3i+1}^3 + x_{3i+2}^3 + x_{3i+3}^3 - x_{3i+1}x_{3i+2}x_{3i+3}\right)\\ &\le \sum_{i=0}^{k-1} \left((3i+2)^3 + (3i+3)^3\right)\\ &= \frac{27}{2}k^4 + 18k^3 + \frac92k^2 - k. \end{align*}

Also, when $x_{3i+1} = 0, x_{3i+2} = 3i+2, x_{3i+3} = 3i+3$ for $i = 0, 1, \cdots, k-1$, we have $F = \frac{27}{2}k^4 + 18k^3 + \frac92k^2 - k$.

We are done.

---

Proof of Fact 1:

Let $f := a^3 + b^3 + c^3 - abc$.

We have \begin{align*} f &\le p^2 a + (p+1)^2 b + (p+2)^2 c - abc \\ &= p^2a + (p+1)^2b + [(p + 2)^2 - ab]c\\ &\le p^2a + (p+1)^2b + [(p + 2)^2 - ab]\cdot (p + 2)\\ &= (p+2)^3 + p^2a + [(p+1)^2 - a(p+2)]b\\ &\le (p+2)^3 + p^2a + [(p+1)^2 - a(p+2)]\cdot (p+1)\\ &= (p+1)^3 + (p+2)^3 - [(p+1)(p+2) - p^2]a\\ &\le (p+1)^3 + (p+2)^3. \end{align*}

Also, when $a = 0, b = p+1, c = p+2$, we have $f = (p+1)^3 + (p+2)^3$.

We are done.