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

Results 16 to 19 of 19

- May 9th 2009, 06:56 PM #16

- Joined
- Apr 2009
- Posts
- 11

- May 9th 2009, 11:33 PM #17

- Joined
- Nov 2005
- From
- someplace
- Posts
- 14,972
- Thanks
- 5

- Jul 28th 2009, 10:11 AM #18

- Joined
- Jul 2009
- Posts
- 193
- Thanks
- 5

This is how i did it...

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

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

so whatever value minimises S would minimise

2S=$\displaystyle (|x-2|+|x-2^{16}|)+(|x-2^2|+|x-2^{15}|)$

$\displaystyle +......+(|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 $\displaystyle (|x-2|+|x-2^{16}|)$ are $\displaystyle 2 \leq x \leq 2^{16}$ and so on.

the intersection of $\displaystyle 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 $\displaystyle 2^8 \leq x \leq 2^9$ so these values would all minimise S.

- Aug 7th 2009, 03:45 PM #19

- Joined
- Aug 2009
- Posts
- 143

Problem: Known $\displaystyle -\infty<x_1<x_2<...<x_{n-1}<x_n<+\infty$, minimize $\displaystyle f(x)=\sum_{i=1}^{n} |x-x_i|$.

Two observations of $\displaystyle f(x)$ are:

(1) It is uni-modal (for odd $\displaystyle n$, 1 minimum point) or almost so (for even $\displaystyle n$, 2 minimum points of equal functional value).

(2) The minimum value can be reached at the nodes $\displaystyle x_i, 1\leq i\leq n$.

With these observations, suppose minimum is reached at $\displaystyle x_k$. Then

$\displaystyle 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)$$\displaystyle =(2k-n-1)x_k+\sum_{i=k+1}^{n} x_i-\sum_{i=1}^{k-1} x_i$

Similarly,

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

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

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

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

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

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