Picking an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$

Question

I've got the following problem:

Tommy has a toy consisting of wooden posts and in each move he can either hit one post (which decreases its height by 1) or pull out a post (which increases its height by one). Tommy wants to set all poles to the same height but he must do that using minimal ammount of moves. How many moves must be made?

An input is a list $[x_1,x_2,...,x_n]$ where $x_i$ is a starting height of pole number $i$.

Mathematically speaking we must find an $m$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $x_i$ is an element of the list $[x_1,x_2,...,x_n]$ and then all we need to do is to calculate this sum. But how to find such an $m$? And if I have a candidate for $m$, how to prove that I am right?

Answer 1

Rearrange the numbers in sorted order so that you have $x_1\le x_2\le \dotsm \le x_n$. Now let $m$ be the median value, $x_{\lceil (n/2)\rceil}$, i.e., the value for which half of the elements are greater than or equal to $m$. This will minimize $\sum_{i=1}^n |x_i-m|$. (If $n$ is even, any value $m$ in the range $x_{\lceil (n/2)\rceil}\le m\le x_{\lceil (n/2)\rceil+1}$ will do for $m$).

For example, if $x_1=1, x_2=2, x_3=4, x_4=8, x_5=16$, the median value will be $m=x_3= 4$ and you'll have $$\begin{array}{ccccccccc} & |x_1-4| & + & |x_2-4| & + & |x_3-4| & + & |x_4-4| & + & |x_5-4|\\ =& |1-4| & + & |2-4| & + & |4-4| & + & |8-4| & + & |16-4|\\ =& 3 & + & 2 & + & 0 & + & 4 & + & 12\\ =& 21 &&&&&&&& \end{array}$$

so the minimum value of the sum will be 21.

It's not too difficult to show that this algorithm is correct: inductive proofs for $n$ even and $n$ odd will do it. To see what's going on, try graphing something like $y=|x-1|+|x-3|$ and looking for the $x$ value(s) that minimize this function.