UNSW MathSoc Championship Q5

For a set $S$ with $n$ elements such that $s_1 < s_2 < \cdots < s_n$ , $\displaystyle \sum_{s \ \in \ S} |x - s|$ is minimized when $x$ is the median of $S$ .

Let's show this intuitively before proving it rigorously.

Intuition

Imagine the given values as trees along a road. The quantity you are trying to minimize is the sum of distances between you and each of the trees.

Suppose that you are standing at the median, and you know the current value of the sum. How will it change if you move in either direction? Note that regardless of which direction you choose, in each moment you will be moving away from at least half of the trees, and towards at most half of the trees. Therefore, the sum of distances can never decrease -- and that means the sum of distances at the beginning had to be optimal.

Proof

Suppose that the set $S$ has $n$ elements, $s_1 < s_2 < \cdots < s_n$ . If $x < s_1$ , then

$\displaystyle \begin{aligned} f(x) = \sum_{s \ \in \ S} |x - s| = \sum_{s \ \in \ S} |s - x| = \sum_{s \ \in \ S} \left(s - x\right) = \sum_{k = 1}^{n} \left(s_k - x\right) \end{aligned}$

As $x$ increases, each term of $f(x)$ decreases until $x$ reaches $x_1$ , so $f(s_1) < f(x)$ for all $x < s_1$ .

Now suppose that $s_ k \leq x \leq x+d \leq s_k + 1$ . Then

$\displaystyle \begin{aligned} f(x + d) & = \sum_{i \ = \ 1}^{k} \left(x + d - s_i\right) + \sum_{i \ = \ k + 1}^{n} \left(s_i - (x + d)\right) \\ & = dk + \sum_{i \ = \ 1}^{k} \left(x - s_i\right) - d(n - k) + \sum_{i \ = \ k + 1}^{n} \left(s_i - x\right) \\ & = d(2k - n) + \sum_{i \ = \ 1}^{k} \left(x - s_i\right) + \sum_{i \ = \ k + 1}^{n} \left(s_i - x\right) \\ & = d(2k - n) + f(x) \end{aligned}$

so $f(x + d) - f(x) = d(2k - n)$ . This is negative if $2k < n$ , zero if $2k = n$ , and positive if $2k > n$ . Thus, on the interval $\left[s_k, s_{k+1}\right]$ ,

$\displaystyle f(x) \ \text{is } \begin{cases} \text{decreasing, } & \text{if } 2k < n \\ \text{constant, } & \text{if } 2k = n \\ \text{increasing, } & \text{if } 2k > n \end{cases}$

In particular, we note that when $2k = n$ , the sum stays constant. What this translates to for our tree analogy is that the sum of the distances does not "tend" toward one direction or another. Finally, we note that since $2k = n$ , $k$ is the median of our set $S$ .

Thus, we have proven that for a set $S$ with $n$ elements such that $s_1 < s_2 < \cdots < s_n$ , $\displaystyle \sum_{s \ \in \ S} |x - s|$ is minimized when $x$ is the median of $S$ . Now let $\displaystyle f(x) = \sum_{n \ = \ 1}^{2017} |x - n|$ . $f(x)$ is minimized when $x$ is the median of the set $S = \{1, 2, 3, \ldots 2016, 2017\}$ . Since $S$ is a uniform distribution, the median equals the mean of the set, so the median is $\displaystyle x = \frac{1 + 2017}{2} = \boxed{1009}$ .