Given a sorted set $S = \{x_1,x_2,...,x_n\}$, find the minimum number of actions to make equal all the elements of the set. Action stands for incrementing or decrementing some element of the set by $1$.
I am claiming that this number is $\sum_{i=1}^n |x_i-m|$ where $m = x_{\lfloor n/2\rfloor}$. To prove the claim I tried the triangle inequality $$\sum_{i=1}^n |x_i-m| \ge \left|\sum_{i=1}^n x_i - n\cdot m\right|$$ I know that the equality of the triangle inequality with two variables would occur when $\text{sgn}(x_1)=\text{sgn}(x_2)$, but I don't know how to proceeed with $n$ variables. The claim seems to be correct for special cases.
- Source: Minimum moves to equal array elements II. (See the picture)
You have to choose a target number $m$, then add to or subtract from each element to get to $m$. You are correct that the number of actions for a given $m$ is $\sum_{i=1}^m|x_i-m|$. If you think about changing the target to $m+1$ you will increase the sum by $1$ for all the elements equal to or below $m$ and decrease the sum by $1$ for all the elements greater than $m$. If over half the elements are above $m$ this is a good thing. If over half the elements are below $m$ decreasing the target is a good thing. Leaving the target unchanged is a good thing when it is the median of the set.