BDMO 2016 National : Problem 4

Discussion on Bangladesh Mathematical Olympiad (BdMO) National
Code Breaker
Posts:1
Joined:Fri Nov 11, 2016 11:28 am
BDMO 2016 National : Problem 4

Unread post by Code Breaker » Fri Nov 11, 2016 12:09 pm

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?

User avatar
Thanic Nur Samin
Posts:176
Joined:Sun Dec 01, 2013 11:02 am

Re: BDMO 2016 National : Problem 4

Unread post by Thanic Nur Samin » Wed Dec 14, 2016 12:48 pm

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}$
Hammer with tact.

Because destroying everything mindlessly isn't cool enough.

Post Reply