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?

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.

• Great! Concise and crystal clear. Thanks for this instructive and inspiring answer. (+1) – Markus Scheuer Feb 20 '17 at 23:37

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*}

• m + $\frac{1}{2}$ or m + $\frac{1}{4}$? – Jens Feb 19 '17 at 22:47
• @Jens: It is $m+\frac{1}{4}$. Thanks! – Markus Scheuer Feb 19 '17 at 22:48

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.

• We need such an analysis. But case 5 is not similar to case 4. If $x_{i-1}=0$ and $x_{i+1}=1$ then $x_i={1\over2}$ is better that $x_i\in\{0,1\}$. – Christian Blatter Feb 19 '17 at 19:00
• @ChristianBlatter Absolutely correct, very interesting slip of a logic (of my logic). Thank you for pointing this out. – Jan Feb 19 '17 at 19:05