# Math Help - Problem 50

1. The minimum is attained at the mean $\dfrac{\sum_{i=1}^{16} 2^i}{16}= \dfrac{2^{16}-1}{16}$

2. Originally Posted by hkito
The minimum is attained at the mean $\dfrac{\sum_{i=1}^{16} 2^i}{16}= \dfrac{2^{16}-1}{16}$
If you tell us why you think the minimum is attained there and what that minimum is we could explain where you went wrong.

CB

3. This is how i did it...

let S= $|x-2|+|x-2^2|+...+|x-2^8|+|x-2^9|+....+|x-2^{15}|+|x-2^{16}|$

and S= $|x-2^{16}|+....+|x-2^9|+|x-2^8|+.......+|x-2|$

so whatever value minimises S would minimise

2S= $(|x-2|+|x-2^{16}|)+(|x-2^2|+|x-2^{15}|)$
$+......+(|x-2^8|+|x-2^9|)+
(|x-2^9|+|x-2^8|)+......+(|x-2^{16}|+|x-2|)$

So if we look at all the values of x which minimises each term then the intersection of the values of x will minimise 2S and S.

looking at the graph of each term as chisigma did we see that all values between the minimum of each of the two terms are minimising values for both terms. since they are linear functions they intersect in the middle.

so the valuse minimising $(|x-2|+|x-2^{16}|)$ are $2 \leq x \leq 2^{16}$ and so on.

the intersection of $2 \leq x \leq 2^{16},2^4 \leq x \leq 2^{15},...,2^8 \leq x \leq 2^9,...,2 \leq x \leq 2^{16}$

is $2^8 \leq x \leq 2^9$ so these values would all minimise S.

4. Problem: Known $-\infty, minimize $f(x)=\sum_{i=1}^{n} |x-x_i|$.

Two observations of $f(x)$ are:
(1) It is uni-modal (for odd $n$, 1 minimum point) or almost so (for even $n$, 2 minimum points of equal functional value).
(2) The minimum value can be reached at the nodes $x_i, 1\leq i\leq n$.

With these observations, suppose minimum is reached at $x_k$. Then
$f(x_k)=\sum_{i=1}^{n} |x_k-x_i|=\sum_{i=1}^{k-1} (x_k-x_i)+\sum_{i=k+1}^{n}(x_i-x_k)$ $=(2k-n-1)x_k+\sum_{i=k+1}^{n} x_i-\sum_{i=1}^{k-1} x_i$

Similarly,
$f(x_{k-1})=(2k-n-3)x_{k-1}+\sum_{i=k}^{n} x_i-\sum_{i=1}^{k-2} x_i$
$f(x_{k+1})=(2k-n+1)x_{k+1}+\sum_{i=k+2}^{n} x_i-\sum_{i=1}^{k} x_i$

$f(x_k)-f(x_{k-1})=(2k-n-2)(x_k-x_{k-1})\leq 0=>2k\leq n+2$

$f(x_{k+1})-f(x_k)=(2k-n)(x_{k+1}-x_k)\geq 0=>2k\geq n$

Therefore, $\frac{n}{2}\leq k \leq \frac{n}{2}+1$

For the present example, $n=16$, so $k=8$ or 9.

Page 2 of 2 First 12