How find the maximum of the value $\sum_{i=1}^{n}x_{i}|x_{i}-x_{i+1}|$ Let $n\ge 4$ be give postive integers,and $x_{i}\in [0,1](i=1,2,\cdots,n)$,find the maximum of the value
$$\sum_{i=1}^{n}x_{i}|x_{i}-x_{i+1}|$$
where $x_{n+1}=x_{1}$
I think the maximum of the value for some $x_{i}=0$ and for some $x_{j}=1$.But How find the maximum?
 A: Let $n\geq3$ be given, and denote by $X$ the set of cyclic sequences $x: \>{\mathbb Z}_n\to[0,1]$.  For $x\in X$ put
$$\|x\|:=\sum_{k=1}^n x_k\>|x_{k+1}-x_k|\ .$$
Let $M\subset X$ be the subset of $x\in X$ with maximal norm. If $x\in M$ then $x$ is not constant, and $\max x_k=1$ (or else $\|x\|$ could be increased by adding a small constant sequence). In the following we put together some "local" properties of sequences $x\in M$. A subsequence of consecutive entries in $x$ is called a window.
${\bf 1.}$ For an $x\in M$ let $(u,v,w)$ be a window with $u\leq v\leq w$. Then $v={u+w\over2}$.
Proof. Only two summands in $\|x\|$ depend on $v$. The function $\phi(v)=u(v-u)+v(w-v)$ collecting these summands  is maximal at $v_*={u+w\over2}\in[u,w]$. As $x\in M$ the claim follows.
${\bf 2.}$ For an $x\in M$ one cannot have a window $(1,1)$.
Proof. If there were $\geq2$ consecutive entries $1$ there would be a window $(u,1,1)$ with $u<1$. This contradicts ${\bf 1}$.
${\bf 3.}$ For an $x\in M$ let $(u,v,w)$ be a window with $u<v$, $\ v>w$. Then $v=1$.
Proof. The function $\phi(v)=u(v-u)+v(v-w)$ has derivative $\phi'(v)=u+(v-w)+v>0$, hence is maximal when $v=1$.
${\bf 4.}$ If $x\in M$ then any entry $1$ in $x$ is immediately followed by a $0$.
Proof. For a window $(1,v,w)$ we have
$$\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.}$ If $x_0=0$ then there is an $r\geq1$ such that
$$0=x_0\leq x_1\leq x_2\leq\ldots\leq x_r,\qquad x_r>x_{r+1}\geq0\ .$$
From ${\bf 1}$ it follows that there is a $t>0$ such that
$$x_k=k\>t\quad(0\leq k\leq r)\ .$$
This implies $x_{r-1}< x_r\>, \ x_{r+1}>x_r\,$, so that ${\bf 3}$ gives $x_r=1$, hence $t={1\over r}$. If $r\geq2$ we now have the window $\bigl(0,{1\over r},{2\over r}\bigr)$. It is easily checked that for $r\geq3$ replacing ${1\over r}$ here by $1$ increases $\|x\|$. This allows to conclude that $r\in\{1,2\}$.
${\bf 6.}$ Altogether it follows that for $x\in M$ the only possible short windows are $$(0,1)\>,\qquad\left(0,\ {1\over2},\ 1\right)\>,\qquad(1,0)\ .$$
Furthermore any substring $\bigl(0,{1\over2},1,(0,1)^r,0,{1\over2},1\bigr)$ is norm-wise majorized by $(0,1)^{r+3}$. It follows that in an $x\in M$ we can have at most one substring $\bigl(0,{1\over2},1\bigr)$.
The elements of $M$ can therefore be characterized as follows:
If $n=2m$ is even then an $x\in M$ is $\ =(0,1)^m$, up to a rotation in ${\mathbb Z}_n$, and if $n=2m+1$ is odd then an $x\in M$ is $\ =\bigl(0,{1\over2},1,(0,1)^{m-1}\bigr)$, up to a rotation. The experimental findings of Markus Scheuer are therewith confirmed.
A: 
Hint: Simulation indicates
  
  
*
  
*$n=2m$:
$m$ elements of $x_i,1\leq i \leq 2m$ are equal to $1$, the other $m$ are equal to $0$ with sum
  \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$ elements of $x_i,1\leq i \leq 2m+1$  are equal to $1$, $m$ are equal to $0$ and one element is equal to $\frac{1}{2}$ with 
  \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*}

A: This is a partial answer.
Let me first argue that in the solution $\{x_{1}^{*},\ldots,x_{n}^{*}\}$, for any $i$, $x_{i}^{*}\in\{0,1\}$.
To see this, focus only on $x_{i-1}^{*}$, $x_{i}^{*}$ and $x_{i+1}^{*}$. The terms that include $x_{i}$ in the objective function are $x_{i-1}^{*}|x_{i-1}^{*}-x_{i}|+x_{i}|x_{i}-x_{i+1}^{*}|$. Now assume that $x_{i}^{*}\in(0,1)$. There are now several cases to consider.
Case 1: $x_{i-1}^{*}=x_{i+1}^{*}=0$. Then the two terms of the objective function are $x_{i}^{2}$, which is not maximized by $x_{i}^{*}\in(0,1)$.
Case 2: $x_{i-1}^{*}=x_{i+1}^{*}=1$. Then the two terms of the objective function are $1-x_{i}+x_{i}(1-x_{i})=-x_{i}^{2}$, which is not maximized by $x_{i}^{*}\in(0,1)$.
Case 3: $x_{i-1}^{*}=x_{i+1}^{*}=c\in(0,1)$. Then the two terms of the objective function are either $c(c-x_{i})+x_{i}(c-x_{i})=c^2-x_{i}^{2}$ or $c(x_{i}-c)+x_{i}(x_{i}-c)=x_{i}^{2}-c^2$, which is not maximized by $x_{i}^{*}\in(0,1)$.
Case 4: $x_{i-1}^{*}>x_{i+1}^{*}$. Then i) if $x_{i}>x_{i-1}$ the two terms in the objective function are strictly increasing in $x_{i}$, ii) if $x_{i}<x_{i+1}$ the two terms in the objective function are strictly decreasing in $x_{i}$, iii) if $x_{i}\in[x_{i+1},x_{i-1}]$ the two terms in the objective function are strictly convex in $x_{i}$.
Case 5: $x_{i-1}^{*}<x_{i+1}^{*}$. Similar to case 4 (note that I am not really thinking about whether some of the cases can be joined together into a more elegant argument).
Hence $x_{i}^{*}\in\{0,1\}$ for any $i$.
With this, I would argue that neither $x_{i}^{*}=0$ for all $i$ nor $x_{i}^{*}=1$ for all $i$ (both give objective equal to zero, which can be improved upon). Hence, you can take $x_{1}^{*}=1$ without loss of generality. Well, maybe this paragraph is not needed.
And I think you can argue that you cannot have $(1,1,1)$ or $(0,0,0)$ in the solution for any triple (switching the middle always strictly improves things). Moreover, you cannot have $(1,1,0,0)$ in the solution for any quadruple ($(1,0,1,0)$ does strictly better).
In fact, it seems that for $n$ even, there are two solutions. Both constructed by alternating $1$s and $0$s starting either from $1$ or $0$. For $n$ odd, doing similar gives you two solutions but then the last and the first position will have the same entry, either $1$ or $0$, and this pair can be anywhere in the solution.
