Proving that median of list $[x_1,x_2,...,x_n]$ minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$ where $m$ is some number

Question

The problem is in the title. Here is a detailed description:

Let's say we have list $[x_i]_{i=1}^{i=n}$ where $x_i\in\Bbb{N}$. I want to pick such $m\in\Bbb{N}$ which minimises the sum $\sum_{i=1}^{i=n} |x_i-m|$.

In my computer science class we had a problem which was equivalent to the upper one. And apparently the answer was that the $m$ we should choose is the median of the list. But no one has proven it, and I have a hard time seeing why that is the case and not for example arithmetic mean of the list.

What strategy should I use in order to prove that?

Answer 1

Hint: The derivative of the sum with respect to $m$ is $$\frac{\partial }{\partial m}\sum_{i=1}^{n}|m-x_i|=\sum_{i=1}^n{}\frac{m-x_i}{|m-x_i|}$$ where $$\frac{m-x_i}{|m-x_i|}=\begin{cases}\phantom{-}1, & m>x_i \\[0.2cm]-1,& m<x_i\end{cases}$$ and therefore the sum (that appears in the derivative) is equal to zero for $m_0$ such that half of the observations are positive (+1) and half of the observations are negative (-1). Thus the median $m_0$ is a critical point. Due to convexity of the absolute value this is a minimum.

(Of course if there exists $x_i=m_0$ then the function is not differentiable at that point, but the reasoning for obtaining a minimum applies).

Answer 2

Note that the function is differentiable at most points. Calculate its derivative at the points of differentiability and observe that the derivative is always an integer. Then figure out where it is zero.