BdMO Online Forum

Consider the set of integers $\{1,2,...,100\}$. Let $\{x_1,x_2,...x_{100}\}$ be some arbitrary arrangement of the integers $\{1,2,...,100\}$ where all of the $x_i$ are different. Find the smallest possible value of the sum
\[ S=|x_2-x_1|+|x_3-x_2|+...+|x_{100}-x_{99}|+|x_1-x_{100}| \]

I could partially solve it. But how to deal with this more accurately?

Mark the $x_i$'s on the number line. Note that $|x_{i+1}-x_i|$ is the distance between the corresponding points on the number line. So, the $S$ is basically the amount of distance you cover if you go from $x_1$ to $x_2$ to $x_3$ $\ldots$ and finally $x_{100}$ and then back to $x_1$. So, basically, you are travelling the whole path from $1$ to $100$ at least twice, and then some more path in some cases. So you have to travel $2\times 99=198$ distance at the very least. this is achieved when $x_i=i$ for all $i$.

So, the answer is $\boxed{198}$