Let $S = \{ s_1, s_2, \dots, s_n \}$ be a set of $n \ge 1$ non-negative integers and $k$ be an integer satisfying $1 \le k < n$. For a subset $S' \subseteq S$ define:
$$f(S') := \sum_{x \in S'} \sum_{y \in S \setminus S'} |x - y|.$$
Task:
Determine $S' \subseteq S$ with $|S'| = k$ such that $f(S')$ is minimum.
My attempt:
I found the following solution which seems to be correct. WLOG assume $s_1 < s_2 < \dots < s_n$ and $2k \le n$. Let $1 \le m \le n$ such that $\max(m, n - (m + 2(k - 1)))$ is minimum, i.e. choose the "middle". Then
$$S' = \left\{ s_m, s_{m + 2}, s_{m + 4}, \dots, s_{m + 2(k - 1)} \right\}$$
has $k$ elements and $f(S')$ is minimum considering all $k$-subsets of $S$. How to prove that?
In case of $k = 1$, the problem is to find $s \in S$ such that
$$f(\{ s \}) = \sum_{y \in S} |y - s|$$
is minimum. It is well-known and not too difficult to show that $s = s_{\left\lfloor \frac{n}{2} \right\rfloor}$, i.e. a median, works here. I don't see an obvious way to extend the proof, though. Any ideas?