8
$\begingroup$

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?

$\endgroup$
5
+50
$\begingroup$

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.

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

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

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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\}$. $\endgroup$ – Christian Blatter Feb 19 '17 at 19:00
  • $\begingroup$ @ChristianBlatter Absolutely correct, very interesting slip of a logic (of my logic). Thank you for pointing this out. $\endgroup$ – Jan Feb 19 '17 at 19:05

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.