Find the minimal value of $\sum\limits_{n=1}^8|x-n|$

Question

Find the minimum value of $( |x-1|+|x-2|...+|x-8|) $

My attempt

Using triangle inequality i.e. $|x-y|≤|x|+|y|$ $|x-1|=|x-1-0|≤|x-1|+0$ $|x-2|=|x-1-1|≤|x-1|+1$ $|x-3| =|x-1-2| ≤|x-1|+2$

...

...

...

$|x-8| =|x-1-7| ≤|x-1|+7$

Adding all these inequalities, $( |x-1|+|x-2|...+|x-8|) $$≤$ $8|x-1| + 28$ Clearly the minimum value is 28 at x=1. The answer is wrong. Also it is intuitive that the x must lie somewhere in between 1 to 8 so that the sum of the distances of x from each number is the least.

What am I doing wrong? How else to approach this question. Are there any other ways?

Answer 1

Your answer is wrong, but there is nothing contradictory with your derivation. You used the inequality $(|x-1|+\cdots+|x-8|)\leq 8|x-1|+28$, which is loose at the optimal solution of $x$. In other words, $x=1$ minimizes $8|x-1|+28$ but not $(|x-1|+\cdots+|x-8|)$, because of the inequality.

A principled way to approach this question is by case analysis on $x$: analyze $x\leq 0$, $0\leq x\leq 1$, $1\leq x\leq 2$, $\cdots$, $x\geq 8$. The objective function would become linear in each of the above-mentioned regions, and the minimizer of a linear function over an interval $[a,b]$ is always attained on the boundary of the interval. Therefore, you only need to evaluate your objective at $x=1,\cdots,x=8$, and one of them would be the minimizer. It is clear that both $x=4$ and $x=5$ minimize your function, with a optimal value of 16.

Answer 2

Using $$|x-a|=x-a+2(a-x)\mathbf 1_{a>x}=a-x+2(x-a)\mathbf 1_{a<x}$$ one sees that, for every $a$, $$|x-a|\geqslant x-a\qquad |x-a|\geqslant a-x$$ hence the sum $S(x)$ to be minimized is such that $$S(x)\geqslant(x-1)+(x-2)+(x-3)+(x-4)+(5-x)+(6-x)+(7-x)+(8-x)=16$$ Remains to show that $16$ is optimal, that is, that there exists $x$ such that $S(x)=16$. Can you do that?

Answer 3

The graph of the function is composed of several joining line segments. The leftmost is for the interval $(-\infty, 1]$, the next line segment is for the interval $[1,2]$,...,the rightmost line segment is for the interval $[8,\infty)$. This is because for $n\in\mathbb{R} $, $x\in[k, k+1]$, $|x-n|$ is either $x-n$ or $~x+n$ in the whole interval. $f(x) $ as a sum of them is a line segment. It is easy to see that $f$ is continuous by considering the left hand and right hand limits of it at integral points.

The slope for the line segment for the interval $[4,5]$ is $0$ and it is where the function attains its minimum.

Take $x=4$. The minimum value is $3+2+1+0+1+2+3+4=16$.

Answer 4

Let $f(x)=\sum\limits_{n=1}^{8}|x-n|.$

Since it's obvious that the graph of $f$ is an union of segments and rays and for $x\rightarrow\infty$ we can not get a minimal value,

we see that the minimal value occurs in the point, where $|.|$ changes a sign.

Thus, $$\min{f}=\min\{f(1),f(2),...,f(8)\}=f(4)=16.$$

Answer 5

Use the triangle inequality: $|x+y|\le |x|+|y|$.

$|x-1|+|8-x|\ge |x-1+8-x|=7$,

$|x-2|+|7-x|\ge |x-2+7-x|=5$,

$|x-3|+|6-x|\ge |x-3+6-x|=3$,

$|x-4|+|5-x|\ge |x-4+5-x|=1$,

Summing we get min $16$.

Answer 6

Let´s try a different route. It is a well know result in statistics that if $X$ is a random variable, the solution for the problem $$\DeclareMathOperator*{\argmin}{arg\,min} k^*= \argmin_k E|X-k|,$$ in which $E(x)$ is the expected value operator, is $k^*=$ median($X$).

As the minimizer for $a f(x)$ is the same as for $f(x)$, if $a>0$ is a constant, then, the minimizers for $$f(k)=\sum_{i=1}^n |k-i|\ \ \ \text{and}\ \ g(x)=\sum_{i=1}^n |k-i|\frac{1}{n}.$$ are the same.

But $g(k)$, in last line, can be interpreted as $g(k)=E|X-k|$, in which $X$ is a random variable assuming values $1,\ldots,n$ with probability $1/n$ each. Therefore the minimizers for $g(k)$ and $f(k)$ are both the median of $X$.

When $n=8$, in the original problem, the median of $X$ is any value between 4 and 5. Just pick $k=4.5$ for instance, and replace in $f(k)$, with $n=8$, to get $$f(4.5)=16.$$

Therefore 16 is the minimum value and the answer for the problem.