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.


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.