A seemingly interesting (easy?) problem came to mind and I thought it would be nice to ask your opinion about it.
Suppose we are going to arrange numbers $0$ to $n$ in a row in such a way that the sum of the difference between adjacent numbers is max. How could we accomplish this? How could we determine the maximum sum of the difference? How about the minimum?
As an example let us take the numbers $0,1,2,3,4$. Let us look at some arrangements:
$0,1,2,3,4$; the difference between the adjacent numbers are $1,1,1,1$ so the sum is $4$
$1,3,4,0,2$; the difference between the adjacent numbers are $2,1,4,2$ so the sum is $9$
$1,4,0,3,2$; the difference between the adjacent numbers are $3,4,3,1$ so the sum is $11$
$3,0,4,1,2$; the difference between the adjacent numbers are $3,4,3,1$ so the sum is $11$
I figured that the arrangement that will give us the minimum sum is the arrangement $1,2,3,…,n$ because all the difference would just be $1$ and their sum is $n-1$.
I think the maximum sum can be attained by arranging the numbers in the following way:
Place the number $n$ between $0$ and $1$. Then place $n-1$ next to $0$ and $n-2$ next to $1$ and so on.
An additional question, if we already know the minimum and maximum would it be possible to always get an arrangement that will give a sum for all the values between the minimum and the maximum? I tried it with $0,1,2,3$ and I was able to find arrangements for all the values between $3$ and $7$.
Maybe this problem has been asked before but I can't find it on the net. Any ideas? Thanks!
Best Answer
I have an idea how to obtain an upper bound which seems to be good. We have to estimate from above the sum $S=\sum_{i=1}^n |a_i-a_{i-1}|$ where the sequence $a_0,\dots, a_n$ is a permutation of the sequence $0,1,\dots,n$. When we open the moduli in the expression for $S$, we obtain $S=\sum_{i=0}^n\varepsilon_i a_i$, where $\sum_{i=0}^n\varepsilon_i=0$ and $\varepsilon_i\in\{-1,1\}$ for $i=0$ or $i=n$ and $\varepsilon_i\in\{-2,0,2\}$ for $1\le i\le n-1$. Suppose that $n=2k+1$ is odd. Now it seems to be true and easily provable that $S$ have the maximum $(n-1)^2/2-1$ when the $\varepsilon$-coefficients at the numbers $0,1,\dots,k-1$ are “-2”, at $k+2,k+3,\dots,n$ are “2”, at $k$ is “-1” and at $k+1$ is “1”. The case when $n$ is even can be considered similarly.