Question about finding the minimum of $|x-1| + |x-2|+|x-4|+|x-8|+|x-16|+|x-32|+|x-64|+|x-128|+\ldots+|x-2^n|$

Question

Hey so I was looking at this problem of finding the minimum of $|x-1|+|x-2|+|x-4|+|x-8|+|x-16|+|x-32|+|x-64|+|x-128|$ and you can find that the minimum occurs when x is from 8 to 16. I noticed that these were the two middle expressions as $8$ and $16$ were the center two powers from the numbers going from $1$ to $128$.

Then I looked at Finding the minimum of $|x-1| + |x-2|+|x-4|+|x-8|+|x-16|+|x-32|+|x-64|+|x-128|+|x-256|$ and you realize making the middle power of two zero or $|x-16|=0$ that minimizes it which means $x=16$ is the minimum.

So I assume that from finding the minimum value of $|x-1| + |x-2|+|x-4|+|x-8|+|x-16|+|x-32|+|x-64|+|x-128|+\ldots+|x-2^n|$ is always going to occur when the middle expression(s) is/are minimzed. In other words when $n$ is even then making $\left|x-2^{n/2}\right|=0$ minimizes it and the same logic for when $n$ is even. I don't know how to say that mathematically, but does anyone know why this is the case and how to prove it?

Answer 1

The slope of $|x-a|$ is $-1$ for $x<a$, and $+1$ for $x>a$. So, if $(a_1,\ldots,a_n)$ is any strictly increasing sequence of real numbers, the slope of

$$|x-a_1|+|x-a_2|+\cdots+|x-a_n|$$

goes from $-n$ to $-n+2$ to $-n+4$ to $\ldots$ to $n-2$ to $n$ as $x$ passes through the points $a_1,\ldots\,a_n$. (At $x=a_i$ the slope is not defined, but the function is continuous, so that doesn't matter to us here.)

So if $n$ is odd, the minimum occurs when the slope goes from negative to positive, at $x=a_{(n+1)/2}$. And if $n$ is even, the minimum occurs where the slope is zero, at $a_{n/2}\le x\le a_{n/2+1}$.

Answer 2

Hint : let $n = 2k+1$ then $f(x) = |x-1| + \ldots + |x-2^n|$ has part $x \in [2^{k} , 2^{k+1}]$, for which $f(x) = C$ (and this $C$ minimize $f(x)$).

If $n = 2k$ then it's easy to construct plot of function, just divide $(-\infty,1] \cup [1,2]\cup\ldots\cup[2^n,\infty)$ and because for $x \in (-\infty,1] ; [1,2]; \ldots ;[2^{k-1},2^k]$ function decrease and only then it increase we may deduce that minimal point is $x = 2^k$

Answer 3

I will solve it for the case where are an odd number of terms (the argument is similar when there are an even number of terms). Suppose that the optimum $x^*$ does not occur where the middle term is zero. Then there must be more powers of two on one side of $x^*$. Wlog suppose there are more terms less than $x^*$. Move $x^*$ some small amount $\epsilon$ to the left i.e. subtract $\epsilon > 0$ from $x^*$. Note that each term $|2^{i} - x|$ with $2^i < x^*$ will lose $\epsilon$ while all terms $|2^{j} - x|$ with $2^{j} > x^*$ will gain $\epsilon$. Since there are more of the former, $x^* - \epsilon$ is a strictly better solution. This contradicts are assumption that $x^*$ was optimal.