Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Math Help - Problem 50

  1. #1
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Problem 50

    An easy one:

    Let x_i=2^i,\ i=1,.., 16

    Find the minimum of the function:

     <br />
f(x)=\sum_{i=1}^{16} |x-x_i|<br />

    (I had thought I had already posted this, did it disapear for a reason or am I just misremembering events )

    CB
    Last edited by CaptainBlack; November 12th 2008 at 12:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    An easy one:

    Let x_i=2^i,\ i=1,.., 16

    Find the minimum of the function:

     <br />
f(x)=\sum_{i=1}^{16} |x-x_i|<br />

    (I had thought I had already posted this, did it disapear for a reason or am I just misremembering events )

    CB
    OK a clue.

    Given the function:

     <br />
f(x)=\sum_{i=1}^{2} |x-x_i|<br />

    where x_2>x_1 what is the minimum of f(x) and where is it achieved.

    CB
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Nov 2008
    Posts
    82
    Quote Originally Posted by CaptainBlack View Post
    An easy one:

    Let x_i=2^i,\ i=1,.., 16

    Find the minimum of the function:

     <br />
f(x)=\sum_{i=1}^{16} |x-x_i|<br />

    (I had thought I had already posted this, did it disapear for a reason or am I just misremembering events )

    CB

    hey mate,

    without going into two much detail, I believe the solution lies between the intersection of |x - 2| = |x - 2^16| which over the region of intersection becomes
    x - 2 = 2^16 - x
    x = 2^15 + 1

    am I completely off the mark? if not please let me know and I will post my full solution,

    Cheers,

    David
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by David24 View Post
    hey mate,

    without going into two much detail, I believe the solution lies between the intersection of |x - 2| = |x - 2^16| which over the region of intersection becomes
    x - 2 = 2^16 - x
    x = 2^15 + 1

    am I completely off the mark? if not please let me know and I will post my full solution,

    Cheers,

    David
    Try writing in English, that is gobbledy gook.

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Nov 2008
    Posts
    82
    Quote Originally Posted by CaptainBlack View Post
    Try writing in English, that is gobbledy gook.

    CB

    CaptainBlack,

    Am I correct in conjecturing that the value of x which minimises f(x) satisfies,

    |x-2| =|x-2^16| ?

    David

    ps - I apologise for any grammatical and or spelling mistakes that may be present in the above statement.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    this problem is for the moderators only! lol (just kidding!)

    suppose a_1 \leq a_2 \leq \cdots \leq a_n, and f(x)=\sum_{i=1}^n |x-a_i|. put: m=\left \lfloor \frac{n}{2} \right \rfloor. prove that: \min f(x)=\sum_{k=1}^m (a_{n+1-k} - a_k).
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by David24 View Post
    CaptainBlack,

    Am I correct in conjecturing that the value of x which minimises f(x) satisfies,

    |x-2| =|x-2^16| ?

    David

    ps - I apologise for any grammatical and or spelling mistakes that may be present in the above statement.
    Well lets see,

    |x-2|=|x-2^{16}|

    implies (assuming 2 \le x \le 2^{16} anyway) that:

    x-2=2^{16}-x

    or:

     <br />
x=2^8-1<br />

    Now lets do some calculations:

    Code:
    >i=1:16;
    >
    >x=[2^8-1:2^8+1]'
              255 
              256 
              257 
    >
    >s=abs(x-2^i);
    >S=sum(s)
           130052 
           130050 
           130050 
    >
    So we conclude that, no your proposed condition does not define the solution.

    CB
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Banned
    Joined
    Nov 2008
    Posts
    82
    Quote Originally Posted by CaptainBlack View Post
    Well lets see,

    |x-2|=|x-2^{16}|

    implies (assuming 2 \le x \le 2^{16} anyway) that:

    x-2=2^{16}-x

    or:

     <br />
x=2^8-1<br />

    Now lets do some calculations:

    Code:
    >i=1:16;
    >
    >x=[2^8-1:2^8+1]'
              255 
              256 
              257 
    >
    >s=abs(x-2^i);
    >S=sum(s)
           130052 
           130050 
           130050 
    >
    So we conclude that, no your proposed condition does not define the solution.

    CB
    CaptainBlack,

    Thanks for your response, I will have to keep working on it.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2008
    From
    France
    Posts
    1,458
    Quote Originally Posted by CaptainBlack View Post
    An easy one:

    Let x_i=2^i,\ i=1,.., 16

    Find the minimum of the function:

     <br />
f(x)=\sum_{i=1}^{16} |x-x_i|<br />

    (I had thought I had already posted this, did it disapear for a reason or am I just misremembering events )

    CB
    Hi,
    By deriving f on each interval [2^j,2^{j+1}] we find
    \frac{df}{dx}=2j-16
    Therefore f is decreasing up to 2^8 (up to j=7) is constant between 2^8 and 2^9 (for j=8) and increasing from 2^9 (from j=9)
    The minimum of f is reached between 2^8 and 2^9
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by running-gag View Post
    Hi,
    By deriving f on each interval [2^j,2^{j+1}] we find
    \frac{df}{dx}=2j-16
    Therefore f is decreasing up to 2^8 (up to j=7) is constant between 2^8 and 2^9 (for j=8) and increasing from 2^9 (from j=9)
    The minimum of f is reached between 2^8 and 2^9
    It can be done more neatly without calculus.

    CB
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Nov 2008
    Posts
    3
    |x-2^i|, where i is a constant, is a continuous function. So, the sum of |x-2^i|, i = 1 to 16, is a continuous function, too.
    As a continuous function, its minimum/maximum is at at its derivative is 0, or where its derivative has a discontinuity from prositive to negative or vice-versa.

    If x-2^i >= 0 (this means x >= 2^i), then |x-2^i| = x-2^i

    If x-2^i < 0 (this means x < 2^i), then |x-2^i| = 2^i-x.

    We can divide the x values in 18 parts.

    Part 1: x <2^1:
    f(x) = sum of (2^i-x), i = 1 to 16 = something - 16*x .This is a line with derivative -16.

    part 2: 2^1 <= x < 2^2:
    f(x) = x-2^1 + sum of (2^1-x), i = 2 to 16 = something - 14*x. This is a line with derivative -14.

    and so on, till part 9: 2^8 <= x < 2^9:
    f(x) = (sum of (x-2^i), i = 1 to 8) + (sum of (2^i-x), i = 9 to 16) = something (no dependence on x). This is a line with derivative 0.

    part 10: 2^9 <= x < 2^10:
    f(x) = (sum of (x-2^i), i = 1 to 9) + (sim of (2^i-x), i = 10 to 16) = something + 2*x. This is a line with derivative 2.

    From part 10 on, the line segments have positive derivative. This means that the minimum of the function is at part 9, and its value at this part is:
    (sum of 2^i, i = 9 to 16) - (sum of 2^i, i = 1 to 8) = 130560 - 510 = 130050
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by lcmarincek View Post
    |x-2^i|, where i is a constant, is a continuous function. So, the sum of |x-2^i|, i = 1 to 16, is a continuous function, too.
    As a continuous function, its minimum/maximum is at at its derivative is 0, or where its derivative has a discontinuity from prositive to negative or vice-versa.

    If x-2^i >= 0 (this means x >= 2^i), then |x-2^i| = x-2^i

    If x-2^i < 0 (this means x < 2^i), then |x-2^i| = 2^i-x.

    We can divide the x values in 18 parts.

    Part 1: x <2^1:
    f(x) = sum of (2^i-x), i = 1 to 16 = something - 16*x .This is a line with derivative -16.

    part 2: 2^1 <= x < 2^2:
    f(x) = x-2^1 + sum of (2^1-x), i = 2 to 16 = something - 14*x. This is a line with derivative -14.

    and so on, till part 9: 2^8 <= x < 2^9:
    f(x) = (sum of (x-2^i), i = 1 to 8) + (sum of (2^i-x), i = 9 to 16) = something (no dependence on x). This is a line with derivative 0.

    part 10: 2^9 <= x < 2^10:
    f(x) = (sum of (x-2^i), i = 1 to 9) + (sim of (2^i-x), i = 10 to 16) = something + 2*x. This is a line with derivative 2.

    From part 10 on, the line segments have positive derivative. This means that the minimum of the function is at part 9, and its value at this part is:
    (sum of 2^i, i = 9 to 16) - (sum of 2^i, i = 1 to 8) = 130560 - 510 = 130050
    As I said previously, this can be done more easily and elegantly without calculus. Also a hint on how to do this has already been posted.

    CB
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Junior Member
    Joined
    Nov 2008
    Posts
    58
    Thanks
    1
    Here's my attempt:
    f(x) measures the distance of x to 16 points, namely 2, 4, 8, 16, ... , 2^16.

    Suppose we let x to be less than 2. Then we can decrease f(x) by increasing x towards 2 since this decreases the distance of x to all 16 points.

    So what happens when we increase x pass 2? We're getting further away from a single point, ie 2, but at the same time, we are decreasing our distance to 15 points. The net effect is a decrease in f(x).

    The key observation here is that if we change x by a fix amount, the change in the distance is the same for all points(some are positive change, while others are negative, but the absolute value is the same).

    This implies that we should keep increasing x to decrease f(x) as long as we are decreasing the distance to more points than the number of points that we are getting further away.

    Following this logic, we arrive at the answer that f(x) is minimum between the region 2^8 and 2^9, which has 8 points less than it and 8 points more.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Member
    Joined
    Jun 2008
    From
    Plymouth
    Posts
    120
    Thanks
    5
    Okay. The derivative of |x-a| is:
    1 if x-a>0
    0 if x=0
    -1 if x-a<0

    Since we have a sum we the derivative of f(x) is the sum of the derivatives of the modulus:f'(x)= \sum _{i=1}^{16} \left(\left|x-x_i\right|\right)'

    If f'(x) is to be 0 we can't have some of the elements |x-x_i| to be zero because then all the other elements can't be zero. We will have 15 elements that can be 1 or -1 and one which is 0 and their sum cannot be 0.

    Suppose we have a number i=n such as for i>n x-x_i<0. This is easy enough to prove x-x_i>x-x_{i+1}. We will also have x-x_i>0 for i<=n since there can't be a zero term. From f'(x)=0 we can conclude that n=8 (8 times 1 and 8 times -1=0).

    So x-x_9<0 for n>8
    x<2^9
    and
    x-x_8>0 for n<=8
    x>2^8

    All that is left is to prove that this is a minimum but I'll leave that to you.

    Don't know if someone has suggested this. I didn't read all the posts.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5
    In order to have an idea about how we can solve the problem let’s consider the minimum of this function…

     f(x)= \sum_ {i=1}^{2} |x-2^{i}| (1)

    … which is represented [in blue] here…

    http://digilander.libero.it/luposabatini/MHF1.bmp

    The (1) is in fact a ‘straight-line function’ the slope of which changes in x=2 and x=4. More exactly, the function starts with negative slope s=-2, in x=2 becames ‘flat’ [ s=0, and for x > 4 the slope is positive [ s=2]. The ‘minimum’ of (1) in fact is not rescticted to a single point, but in extended to the interval 2 \le x \le 4, where is f(x)=2. In similar way we can ‘attach’ the proposed problem, i.e. finding the minimum of…

     f(x)= \sum_ {i=1}^{16} |x-2^{i}| (2)

    As the (1), the (2) is also ‘straight-line’ . In x=0 is…

     f(0)= \sum_ {i=1}^{16} 2^{i} = 2 \cdot (2^{16}-1)=131070

    The functions starts with negative slope s=-16 and each time that x=2^{i} the slope is increased by +2. So we have…

    x=0, s=-16; x=2, s=-14; x=4, s=-12;\dots; x=2^{7}, s=-2; x=2^{8}, s=0;\dots

    So the functions become ‘flat’ in the interval  256 \le x \le 512 and here exhibits its ‘minimum’ which is [if no mistakes of mine…] …

    f(2^{8})= \sum_{i=1}^{16} |2^{8}-2^{i}|= 2\cdot (2^{8}-1)^ {2}= 130050

    Regards
    Last edited by chisigma; March 12th 2009 at 03:05 AM. Reason: correction
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Search Tags


/mathhelpforum @mathhelpforum