Consider the set of integers $ \left \{ 1, 2, \dots , 100 \right \} $. Let $ \left \{ x_1, x_2, \dots , x_{100} \right \}$ be some arbitrary arrangement of the integers $ \left \{ 1, 2, \dots , 100 \right \}$, where all of the $x_i$ are different. Find the smallest possible value of the sum $$S = \left | x_2 - x_1 \right | + \left | x_3 - x_2 \right | + \cdots+ \left |x_{100} - x_{99} \right | + \left |x_1 - x_{100} \right | .$$
Problem
Source: BdMO National 2016
Tags: number theory, algebra, Bdmo, contests
J25201
27.02.2019 03:41
The answer is 198. $\quad$
NoDealsHere
27.02.2019 04:06
J25201 wrote: The answer is 198. $\quad$ what
Olympus_mountaineer
27.02.2019 04:26
NoDealsHere wrote: J25201 wrote: The answer is 198. $\quad$ what $198$
Holmes777
28.02.2019 21:22
how?any explanation?
amrit1968
26.09.2019 18:15
any answer to this?
T-Rex
01.07.2020 19:42
$|x_{(i+1)}-x_i|=$ Distance between two points on the number line. The minimum distance will be if the points are consecutive... So $x_i=i$ So the answer is: $198$
pie854
14.11.2024 07:43
The minimum is $198$. Necessity: Suppose that $\{x_i,x_j\}=\{100,1\}$ where $1\leq i<j\leq 100$. Then notice that \begin{align*} S & = |x_2-x_1|+\dots+|x_i-x_{i-1}|+|x_{i+1}-x_i|+\dots+|x_j-x_{j-1}|+|x_{j+1}-x_j|+\dots+|x_1-x_{100}| \\ & \geq |x_2-x_1+x_3-x_2+\dots+x_i-x_{i-1}|+|x_{i+1}-x_i+x_{i+2}-x_{i+1}+\dots+x_j-x_{j-1}|+|x_{j+1}-x_j+x_{j+2}-x_{j+1}+\dots+x_1-x_{100}| \\ & = |x_i-x_1|+|x_j-x_i|+|x_1-x_j| \\ & \geq |x_i-x_1+x_1-x_j|+|x_j-x_i| = 2|x_j-x_i|. \end{align*}As $|x_j-x_i|=100-1=99$, it follows that $S\geq 2\cdot 99=198$. Sufficiency: Take $x_i=i$ for $1\leq i\leq 100$, then $S=2\cdot 99=198$.