Cómo encontrar el máximo de el valor de $\sum_{i=1}^{n}x_{i}|x_{i}-x_{i+1}|$

Question

Deje $n\ge 4$ ser enteros positivos,y $x_{i}\in [0,1](i=1,2,\cdots,n)$,de encontrar el máximo del valor $$\sum_{i=1}^{n}x_{i}|x_{i}-x_{i+1}|$$ donde $x_{n+1}=x_{1}$

Creo que el máximo del valor de algunos de los $x_{i}=0$ y, para algunos,$x_{j}=1$.Pero, ¿Cómo encontrar el máximo?

Answer 1

Deje $n\geq3$, y denotan por $X$ el conjunto de secuencias cíclicas $x: \>{\mathbb Z}_n\to[0,1]$. Para $x\in X$ poner $$\|x\|:=\sum_{k=1}^n x_k\>|x_{k+1}-x_k|\ .$$ Deje $M\subset X$ ser el subconjunto de $x\in X$ con la máxima norma. Si $x\in M$ $x$ no es constante, y $\max x_k=1$ (o más $\|x\|$ podría ser aumentado por la adición de una pequeña constante de la secuencia). A continuación vamos a poner juntos algunos de los "locales" de las propiedades de las secuencias de $x\in M$. Una larga de entradas consecutivos en $x$ se llama a una ventana.

${\bf 1.}$ $x\in M$ Deje $(u,v,w)$ ser una ventana con $u\leq v\leq w$. A continuación,$v={u+w\over2}$.

Prueba. Sólo dos sumandos en $\|x\|$ dependen de la $v$. La función de $\phi(v)=u(v-u)+v(w-v)$ la recogida de estos sumandos es máxima en $v_*={u+w\over2}\in[u,w]$. Como $x\in M$ la demanda de la siguiente manera.

${\bf 2.}$ $x\in M$ Uno no puede tener una ventana de $(1,1)$.

Prueba. Si no se $\geq2$ entradas consecutivos $1$ habría una ventana de $(u,1,1)$$u<1$. Esto contradice ${\bf 1}$.

${\bf 3.}$ $x\in M$ Deje $(u,v,w)$ ser una ventana con $u<v$, $\ v>w$. A continuación,$v=1$.

Prueba. La función de $\phi(v)=u(v-u)+v(v-w)$ ha derivado $\phi'(v)=u+(v-w)+v>0$, por lo tanto es máxima cuando $v=1$.

${\bf 4.}$ Si $x\in M$, a continuación, cualquier entrada de $1$ $x$ es seguido inmediatamente por una $0$.

Prueba. Para una ventana de $(1,v,w)$ hemos $$\phi(v)=1-v+v|w-v|=1-v\bigl(1-|w-v|\bigr)\leq1\ ,$$and $\phi(v)=1$ iff $v=0$ or $|w-v|=1$. The latter implies $\{v,w\}=\{0,1\}$. Here $v=0$ is fine, whereas $v=1$ is forbidden according to ${\bf 2}$.

${\bf 5.}$ Si $x_0=0$, entonces hay un $r\geq1$ tal que $$0=x_0\leq x_1\leq x_2\leq\ldots\leq x_r,\qquad x_r>x_{r+1}\geq0\ .$$ De ${\bf 1}$ se deduce que hay un $t>0$ tal que $$x_k=k\>t\quad(0\leq k\leq r)\ .$$ Esto implica $x_{r-1}< x_r\>, \ x_{r+1}>x_r\,$, por lo que el ${\bf 3}$ da $x_r=1$, por lo tanto $t={1\over r}$. Si $r\geq2$ ahora tenemos la ventana de $\bigl(0,{1\over r},{2\over r}\bigr)$. Es fácil comprobar que para $r\geq3$ sustitución de ${1\over r}$ aquí por $1$ aumenta el $\|x\|$. Esto permite concluir que el $r\in\{1,2\}$.

${\bf 6.}$ Totalmente de ello se sigue que para $x\in M$ la única posible a corto windows se $$(0,1)\>,\qquad\left(0,\ {1\over2},\ 1\right)\>,\qquad(1,0)\ .$$ Además cualquier subcadena $\bigl(0,{1\over2},1,(0,1)^r,0,{1\over2},1\bigr)$ es la norma sabio majorized por $(0,1)^{r+3}$. De ello se deduce que en un $x\in M$ que puede tener en la mayoría de una subcadena $\bigl(0,{1\over2},1\bigr)$.

Los elementos de $M$ por lo tanto puede ser caracterizada de la siguiente manera:

Si $n=2m$ es incluso entonces un $x\in M$$\ =(0,1)^m$, hasta una rotación en ${\mathbb Z}_n$, y si $n=2m+1$ es impar entonces un $x\in M$$\ =\bigl(0,{1\over2},1,(0,1)^{m-1}\bigr)$, hasta una rotación. Los resultados experimentales de Markus Scheuer son los mismos confirmado.

Answer 2

Sugerencia: Simulación indica

• $n=2m$:

  $m$ elementos de $x_i,1\leq i \leq 2m$ son igual a $1$, el otro $m$ son igual a $0$ con suma \begin{align*} \sum_{i=1}^{2m-1}x_i|x_{i}-x_{i+1}|+x_{2m}|x_{2m}-x_1|=m \end{align*}

• $n=2m+1$:

  $m$ elementos de $x_i,1\leq i \leq 2m+1$ son iguales a $1$, $m$ son iguales a $0$ y un elemento es igual a $\frac{1}{2}$ con \begin{align*} \sum_{i=1}^{2m}x_i|x_{i}-x_{i+1}|+x_{2m+1}|x_{2m+1}-x_1|=m+\frac{1}{4} \end{align*}

Answer 3

Esta es una respuesta parcial.

Permítanme en primer lugar decir que, en la solución de $\{x_{1}^{*},\ldots,x_{n}^{*}\}$, para cualquier $i$, $x_{i}^{*}\in\{0,1\}$.

Para ver esto, se centran sólo en $x_{i-1}^{*}$, $x_{i}^{*}$ y $x_{i+1}^{*}$. Los términos que incluyen a $x_{i}$ en la función objetivo se $x_{i-1}^{*}|x_{i-1}^{*}-x_{i}|+x_{i}|x_{i}-x_{i+1}^{*}|$. Supongamos ahora que $x_{i}^{*}\in(0,1)$. Ahora hay varios casos a considerar.

Caso 1: $x_{i-1}^{*}=x_{i+1}^{*}=0$. A continuación, los dos términos de la función objetivo se $x_{i}^{2}$, que no está maximizada por $x_{i}^{*}\in(0,1)$.

Caso 2: $x_{i-1}^{*}=x_{i+1}^{*}=1$. A continuación, los dos términos de la función objetivo se $1-x_{i}+x_{i}(1-x_{i})=-x_{i}^{2}$, que no está maximizada por $x_{i}^{*}\in(0,1)$.

Caso 3: $x_{i-1}^{*}=x_{i+1}^{*}=c\in(0,1)$. A continuación, los dos términos de la función objetivo son o $c(c-x_{i})+x_{i}(c-x_{i})=c^2-x_{i}^{2}$ o $c(x_{i}-c)+x_{i}(x_{i}-c)=x_{i}^{2}-c^2$, que no está maximizada por $x_{i}^{*}\in(0,1)$.

Caso 4: $x_{i-1}^{*}>x_{i+1}^{*}$. Entonces i) si $x_{i}>x_{i-1}$ los dos términos en la función objetivo son estrictamente creciente en a $x_{i}$, ii) si $x_{i}<x_{i+1}$ los dos términos en la función objetivo son estrictamente decreciente en a $x_{i}$, iii) si $x_{i}\in[x_{i+1},x_{i-1}]$ los dos términos en la función objetivo son estrictamente convexa en $x_{i}$.

Caso 5: $x_{i-1}^{*}<x_{i+1}^{*}$. Similar a la del caso 4 (tenga en cuenta que yo no soy realmente pensar acerca de si algunos de los casos pueden ser unidas en una forma más elegante argumento).

Por lo tanto $x_{i}^{*}\in\{0,1\}$ cualquier $i$.

Con esto, yo diría que ni $x_{i}^{*}=0$ todos los $i$ ni $x_{i}^{*}=1$ todos los $i$ (ambos dan objetivo igual a cero, lo que puede ser mejorado). Por lo tanto, usted puede tomar $x_{1}^{*}=1$ sin pérdida de generalidad. Bueno, tal vez este párrafo no es necesario.

Y creo que se puede argumentar que no se puede tener $(1,1,1)$ o $(0,0,0)$ en la solución para cualquier triple (cambiar el medio siempre estrictamente mejora las cosas). Por otra parte, usted no puede tener $(1,1,0,0)$ en la solución para cualquier cuádruple ($(1,0,1,0)$ no estrictamente mejor).

De hecho, parece que para $n$ incluso, hay dos soluciones. Ambas construidas por la alternancia de $1$s y $0$s, comenzando desde $1$ o $0$. Para $n$ impar, haciendo similar le da dos soluciones, pero, a continuación, la última y la primera posición tendrá la misma entrada, $1$ o $0$, y este par puede estar en cualquier parte en la solución.