Prove:$|x-1|+|x-2|+|x-3|+\cdots+|x-n|\geq n-1$

Solution 1:

Actually, $|x-n| + |x-1| = |n-x| + |x-1| \geq |n-1|=n-1$. Don't need the other terms.

Your first proof is correct. You have to take some care moving from $U^2\geq V^2$ to $U\geq V$, but in this case, $U=|t-1|$ is non-negative.

Solution 2:

Note that the sum $F(x)=|x-1|+|x-2| +\cdots +|X-n|$ is the sum of the distances from $x$ to the points $1,2,\dots,n$. Draw the $n$ points $1,2,3,\dots,n$ on the number line, taking $n$ say $7$ or $8$.

Imagine that a particle $P$ starts far to the left of $1$, and travels to the right.

Until it hits $x=1$, the sum is of the distances of $P$ from $1,2,\dots, n$ is decreasing. At $x=1$ it becomes $1+2+\cdots+(n-1)$.

As we travel from $1$ to $2$, the function $F(x)$ is decreasing. For each tiny step $s$ we take to the right increases our distance from $1$ by $s$, but it decreases our distance from each of $2, 3,\dots,n$ by $s$. So each tiny step $s$ we take decreases $F(x)$ by $(n-1)s-s$.

If $n$ is not too small, this decrease continues. For each small step $s$ we take from $2$ towards $3$ increases our distance from $1$ and $2$ by $s$, and decreases our distance from each of the other points by $s$, for a decrease of $(n-2)s-2s$.

If $n$ is odd, $F(x)$ keeps decreasing until $x=\frac{n+1}{2}$, and then by symmetry $F(x)$ starts to increase. If $n$ is even, then $F(x)$ reaches a minimum at all points between $\frac{n}{2}$ and $\frac{n+1}{2}$.

For $n$ odd, say $n=2k+1$, the minimum value of $F(x)$ is $2(1+2+3+\cdots +k)$. This is $k(k+1)$. For $n$ even, say $n=2k$, the minimum value of $F(x)$ is $(1+2+\cdots +(k-1))+(1+2+\cdots +k)$. This is $k^2$.

Back to the question in the post.

We want to show that if $n$ is odd, say $n=2k+1$, then $k(k+1) \ge 2k$, and that if $n$ is even, say $2k$m then $k^2\ge 2k-1$. Both of these are obvious.

Remark: We wrote out a solution in order to emphasize the geometry of the situation.

Generalization: Suppose that instead of $1,2,\dots,n$ we have numbers $a_1 \le a_2\le a_3\le \cdots \le a_n$.

Play the same walking game. If $n=2k+1$ is odd, then $F(x)$ reaches its minimum at $x=k+1$. The number $a_{k+1}$ is the median of our $n$ numbers $a_1,\dots, a_n$.

If $n$=2k is even, then $F(x)$ reaches a minimum at all points between $x=k$ and $x=k+1$. Any such $x$ can be viewed as a median of the $a_i$.

Solution 3:

After the answer of Thomas Andrews my answer appears to be dispensable. But I'll leave it here as a poor alternative. Here a proof valid for any $ x $ since $ n $ is even. For the case $ n $ odd simply discard the parcel | x-n |. \begin{align} |x-1|+|x-2|+|x-3|+\ldots+|x-n| = & |x-1|+|2-x|+|x-3|+ \\ + & \ldots+|(-1)^{n+1}x+(-1)^{n}n| \\ \geq & \bigg[(1-x)+(x-2)+(3-x)+ \\ + & \ldots+(-1)^{n}x+(-1)^{n+1}n\bigg] \\ = & (-1)^1+(-1)^{2}2+(-1)^{3}3+(-1)^{4}4+\ldots \\ + & (-1)^{(n-1)}(n-1)+n(-1)^{n} \\ = & \frac{n}{2}+n(-1)^{n}= \frac{n}{2}+n\geq n \end{align}

Solution 4:

(Edited)

Given a real-valued data set ${\bf y}=(y_k)_{1\leq k\leq n}$ the function $$f(x):=\sum_{k=1}^n |x-y_k|$$ assumes its minimum at the median $\mu$ of ${\bf y}$. When $y_1\leq y_2\leq \ldots\leq y_n$ and $n=2m+1$ then $\mu=y_{m+1}$ (the "middle value"), and if $n=2m$ then $f$ is actually constant on the interval $[y_m,y_{m+1}]$, and one defines $\mu:=(y_m+y_{m+1})/2$.

Proof. When there are $r$ more $y_k$ to the right of $x$ than to the left of $x$ then increasing $x$ by $\Delta x$ will decrease $f$ by $r\cdot\Delta x$, and similarly, when there are $r$ more $y_k$ to the left of $x$ than to the right of $x$ then increasing $x$ by $\Delta x$ will increase $f$ by $r\cdot \Delta x$.$\qquad\square$

It follows that your sum $s(x)$ is minimal at $x={n+1\over2}$. It is then easily computed to $s_{\min}=n^2/4$ when $n$ is even and $s_{\min}=(n^2-1)/4$ when $n$ is odd.

When $n=1$ we have $s_{\min}=0=n-1$, and in the case $n=2$ we have $s_{\min}=1=n-1$. For $n\geq3$ we can argue as follows: $$s_{\min}\geq{n^2-1\over 4}={(n-2)^2-1\over4}+n-1\geq n-1\ .$$