2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Let $f(m)$ be the number of poles that is higher than $m$. What can you say about the behavior of $f$? How does the sum change as you increase/decrease $m$? $\endgroup$ – Tom van der Zanden Dec 14 '14 at 21:38
  • $\begingroup$ Thus question has been asked before at least once. $\endgroup$ – Yuval Filmus Dec 15 '14 at 4:03
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.