## Task 6A - 171246A

Let $n$ be a positive number, $\left(a_{1}, \ldots, a_{n}\right)$ be an $n$-tuple of real numbers with $a_{1} \leq a 2 \leq \ldots \leq a_{n}$.

Investigate whether there exists a real number $x$ such that the number

$$
z=\left|x-a_{1}\right|+\left|x-a_{2}\right|+\ldots+\left|x-a_{n}\right|
$$

is as small as possible.

If such an $x$ exists, determine all real numbers $x$ with this property and give the corresponding minimal value of $z$.
The function

$$
f(x)=\sum_{i=1}^{n}\left|x-a_{i}\right|
$$

is defined on $(-\infty, \infty)$ and, as the sum of finitely many continuous functions, is continuous. The problem asks about the existence of a minimum and, if one exists, the set of minimal points.

For $x-a_{1} \leq 0$, it follows that $x-a_{i} \leq 0$ for $i=1, \ldots, n$, i.e.,

$$
f(x)=\sum_{i=1}^{n}-\left(x-a_{i}\right)=-n x+c_{0} \quad \text { with } \quad c_{0}=\sum_{i=1}^{n} a_{i}
$$

The graph of the function in $\left(-\infty, a_{1}\right)$ is a ray with a slope of $-n$, so for $x \rightarrow-\infty$ we have $f(x) \rightarrow \infty$. For $x-a_{n} \geq 0$, it follows analogously that $f(x)=n x-c_{0}$; the graph of $f(x)$ in $\left(a_{n}, \infty\right)$ is a ray with a slope of $n$, and for $x \rightarrow \infty \quad f(x) \rightarrow \infty$.

Thus, there exists a real number $R>0$ such that for $x \in[-R, R]$, $f(x)R$. By a theorem of Weierstrass, there then exists in the closed interval $[-R, R]$ a point $x^{*}$ where the continuous function $f(x)$ attains its minimum over $(-\infty, \infty)$.

This solves the first part of the problem.

For $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$, we distinguish two cases:

If $a_{i}=a_{1}$ for $i=1, \ldots, n$, then it is clear that $f\left(a_{1}\right)=\min f(x)$; the value of the minimum is then $f\left(a_{1}\right)=0$ and the set of minimal points is $\left\{a_{1}\right\}$.

Otherwise, there exist $i, k \in\{1, \ldots, n\}$ with $i<k$, where $k$ is the smallest index with $a_{i} \neq a_{k}$. For $x \in\left(a_{i}, a_{k}\right)$, we have

$$
\begin{gathered}
x-a_{1} \geq \ldots \geq x-a_{i} \geq 0 \quad ; \quad 0 \geq x-a_{i+1} \geq \ldots \geq x-a_{n} \quad \text {, so that } \\
f(x)=\sum_{\mu=1}^{i} x-a_{\mu}+\sum_{\mu=i+1}^{n}-\left(x-a_{\mu}\right)=i x-(n-i) x-\sum_{\mu=1}^{i} a_{\mu}+\sum_{\mu=i+1}^{n} a_{\mu}=(2 i-n) x+c_{i}
\end{gathered}
$$

The graph of $f(x)$ is thus a line segment in each such interval; the minimum over each such interval $\left[a_{i}, a_{k}\right]$ is attained at $a_{i}$ if the slope $(2 i-n)$ of the line segment is not negative, and at $a_{k}$ if the slope is not positive.

In summary, (using the fact that $2 i-n \geq 0$ if and only if $i\left[\frac{n+1}{2}\right]$), this can be stated as follows:

The function $f(x)$ over $(-\infty, \infty)$ is piecewise linear with non-positive slope for $x \in\left(-\infty, a_{\left[\frac{n+1}{2}\right]}\right)$; the minimum is attained at $a_{\left[\frac{n+1}{2}\right]}$ due to continuity.

For $x \in\left(a_{\left[\frac{n+2}{2}\right]}, \infty\right)$, $f(x)$ is a piecewise linear function with non-negative slope; the minimum is attained at $a_{\left[\frac{n+2}{2}\right]}$ due to continuity.

If $n$ is an odd number, then $a_{\left[\frac{n+1}{2}\right]}=a_{\left[\frac{n+2}{2}\right]}$, and we have

$$
\min f(x)=f\left(a_{\left[\frac{n+1}{2}\right]}\right)=\sum_{\mu=1}^{\frac{n+1}{2}} a_{n-\mu+1}-a_{\mu}
$$

the set of minimal points is $\left\{a_{\left[\frac{n+1}{2}\right]}\right\}$.

If $n$ is an even number, then for $x \in\left[a_{\left[\frac{n+1}{2}\right]}, a_{\left[\frac{n+2}{2}\right]}\right]$, since the slope of the line in this interval is 0, we have

$$
f(x)=\text { const }=\min f(x)=-\sum_{\mu=1}^{\frac{n}{2}} a_{\mu}+\sum_{\mu=\frac{n}{2}+1}^{n} a_{\mu}
$$

is; the set of minimal points is $\left[a_{\left[\frac{n+1}{2}\right]}, a_{\left[\frac{n+2}{2}\right]}\right]$ (which may consist of a single point).

## Adapted from $[3]$