What is the biggest possible sum $|X_1-X_2|+|X_2-X_3|+\cdots+|X_{n-1}-X_n|$ where $X_1,X_2,\cdots,X_n$ are first $n$ positive integers?

Question

What is the biggest possible sum $|X_{1}-X_{2}|+|X_{2}-X_{3}|+\cdots+|X_{n-1}-X_{n}|$ where $X_{1},X_{2},\cdots,X_{n}$ are first $n$ positive integers?

Answer 1

Be greedy. $n$ should go next to $1,2$, then $n-1$ next to $1$ and so on. There are other arrangements that give the same sum, but none better. For $n=12$ it gives $7,5,9,3,11,1,12,2,10,4,8,6$ for $2+4+6+8+10+11+10+8+6+4+2$ and for $n=13$ it gives $8,5,10,3,12,1,13,2,11,4,9,6,7$ for $3+5+7+9+11+12+11+9+7+5+3+1$ The patterns in the elements of the sums should be clear.

Answer 2

Note that $$Y:=\sum_{i=1}^{n-1}\,\left|X_i-X_{i+1}\right|=\sum_{i=1}^{n-1}\,X_{S(i)}-\sum_{i=1}^{n-1}\,X_{T(i)}\,,$$ where $\big\{S(i),T(i)\big\}=\{i,i+1\}$ and $X_{S(i)}>X_{T(i)}$ for each $i=1,2,\ldots,n-1$. Observe that each integer in $\{1,2,\ldots,n\}$ must appear at least once but at most twice amongst $$X_{S(1)},X_{S(2)},\ldots,X_{S(n-1)},X_{T(1)},X_{T(2)},\ldots,X_{T(n-1)}\,.$$

Consequently, $$\sum_{i=1}^{n-1}\,X_{S(i)}\leq n+n+(n-1)+(n-1)+\ldots+ \Biggl(n+1-\left\lceil\frac{n-1}{2}\right\rceil\Biggr)\tag{*}$$ and $$\sum_{i=1}^{n-1}\,X_{T(i)}\geq 1+1+2+2+\ldots+\left\lceil\frac{n-1}{2}\right\rceil\,.\tag{#}$$ Hence, if $n$ is an even positive integer, then $$\begin{align}\sum_{i=1}^{n-1}\,\left|X_i-X_{i+1}\right|&\leq 2\Big((n-1)+(n-3)+\ldots+5+3+1\Big)-1\\&=\frac{n^2}{2}-1=\left\lfloor\frac{n^2}{2}\right\rfloor-1\,.\end{align}$$ There exists a configuration $(X_1,X_2,\ldots,X_n)$ with this sum, namely, $$\left(X_1,X_2,\ldots,X_n\right):=\left(\frac{n}{2},n,\frac{n}{2}-1,n-1,\frac{n}{2}-2,n-2,\ldots,1,\frac{n}{2}+1\right)\,.$$ If I am not mistaken, there are $2\,\Biggl(\left(\dfrac{n}{2}-1\right)!\Biggr)^2$ maximizing configurations for even $n$.

If $n>1$ is an odd integer, then $$\sum_{i=1}^{n-1}\,\left|X_i-X_{i+1}\right|\leq 2\Big((n-1)+(n-2)+\ldots+4+2\Big)=\frac{n^2-1}{2}\,.$$ The inequality cannot become an equality because the number $\dfrac{n+1}{2}$ does not appear as a summand on the right-hand side of (*), as well as on the right-hand side of (#), but each integer from $1$ to $n$ must show up amongst $X_{S(i)}$ and $X_{T(i)}$ at least once. Thus, at least one of the inequalities (*) and (#) cannot become an equality. Ergo, we must indeed have $$\sum_{i=1}^{n-1}\,\left|X_i-X_{i+1}\right|\leq \frac{n^2-1}{2}-1=\left\lfloor\frac{n^2}{2}\right\rfloor-1\,.$$ There exists a configuration with this sum, i.e., $$\left(X_1,X_2,\ldots,X_n\right):=\left(\frac{n-1}{2},n,\frac{n-3}{2},n-1,\frac{n-5}{2},\ldots,1,\frac{n+3}{2},\frac{n+1}{2}\right)\,.$$ If I am not mistaken, there are $4\,\left(\dfrac{n-3}{2}\right)!\,\left(\dfrac{n-1}{2}\right)!$ maximizing configurations for odd $n\geq 3$.

It can also be shown that the minimum value of $Y$ is $n-1$. The minimum value can be achieved in precisely two ways: $$\left(X_1,X_2,\ldots,X_{n-1},X_n\right)=(1,2,\ldots,n-1,n)$$ and $$\left(X_1,X_2,\ldots,X_{n-1},X_n\right)=(n,n-1,\ldots,2,1)\,.$$

---

Here are all maximizing configurations for $n=2,3,4,5,6$.

$n=2$: $(1,2)$ and $(2,1)$.

$n=3$: $(1,3,2)$, $(2,3,1)$, $(2,1,3)$, and $(3,1,2)$.

$n=4$: $(2,4,1,3)$ and $(3,1,4,2)$.

$n=5$: $(2,4,1,5,3)$, $(2,5,1,4,3)$, $(3,4,1,5,2)$, $(3,5,1,4,2)$, $(3,1,5,2,4)$, $(3,2,5,1,4)$, $(4,1,5,2,3)$, and $(4,2,5,1,3)$.

$n=6$: $(3,5,1,6,2,4)$, $(3,5,2,6,1,4)$, $(3,6,1,5,2,4)$, $(3,6,2,5,1,4)$, $(4,1,5,2,6,3)$, $(4,2,5,1,6,3)$, $(4,1,6,2,5,3)$, and $(4,2,6,1,5,3)$.

---

If you want to maximize the sum $$F:=\sum_{i=1}^n\,\left|X_i-X_{i+1}\right|\,,$$ where $X_{n+1}:=X_1$, then the same procedure works. The maximum value of $F$ is $\left\lfloor\dfrac{n^2}{2}\right\rfloor$. For an even integer $n\geq 2$, there are $2\,\Biggl(\left(\dfrac{n}{2}\right)!\Biggr)^2=2\,\left\lceil\dfrac{n}{2}\right\rceil !\,\left\lfloor\dfrac{n}{2}\right\rfloor!$ maximizing configurations. For an odd integer $n\geq 3$, there are $2\,\left(\dfrac{n+1}{2}\right)!\,\left(\dfrac{n-1}{2}\right)!=2\,\left\lceil\dfrac{n}{2}\right\rceil !\,\left\lfloor\dfrac{n}{2}\right\rfloor!$ maximizing configurations.

The minimum value of $F$ is $2(n-1)$. For $n>2$, this can be achieved in precisely $2n$ ways, namely, when $(X_1,X_2,\ldots,X_{n-1},X_n)$ is a cyclic permutations of $(1,2,\ldots,n-1,n)$ or a cyclic permutation of $(n,n-1,\ldots,2,1)$. For $n=2$, there are only two ways: $(X_1,X_2)=(1,2)$ or $(X_1,X_2)=(2,1)$.