How find the maximum of the value $\sum_{i=1}^{n}x_{i}|x_{i}-x_{i+1}|$

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.