(Hard.) Suppose x1,...,xn are real numbers. Suppose n is odd and the xi are all distinct. There is a unique median µ: the middle number when the x’s are arranged in increasing order. Let c be a real number. Show that f

(c) = n i=1 |xi −c|, as a function of

c, is minimized when c = µ.

Hints. You can’t do this by calculus, because f isn’t differentiable.

Instead, show that f

(c) is (i) continuous, (ii) strictly increasing as c increases for c>µ, i.e., µ

(iii) strictly decreasing as c increases for c<µ. It’s easier to think about claims (ii) and (iii) when c differs from all the x’s. You may as well assume that the xi are increasing with i. If you pursue this line of reasoning far enough, you will find that f is linear between the x’s, with corners at the x’s. Moreover, f is convex, i.e., f [(x + y)/2] ≤

[f (x) + f (y)]/2.