Proving the Minimum of a Summation: Solving for f(x) with n Odd and Even Cases

[holezch]

Homework Statement

of $$f(x) = \sum$$ | x - a_i |
( i = 1 to n )

where
a_1 < a_2 < ... < a_n

The Attempt at a Solution

I believe I have proven that if n is odd then the minimum is as ceiling a_(n/2) or a_(n+1)/2. The book says a_(n-1)/2 though, but I think it's wrong.. if you actually tried an example , f( a_(n+1)/2 ) < f ( a_(n-1)/2 ). take n = 5 and a_i's = 1,2,3,4,5 for example
Also, for my even case, I have that the minimum occurs at both a_n/2 and a_n/2 + 1. Roughly speaking, if you introduce a new point that's a_mid( a_n/2 , a_n/2 + 1 ) then we have an odd case and the minimum as I've shown before will be the most middle point, a_mid( a_n/2 , a_n/2 + 1 ) .. et c I'm fairly sure that I have it right so I'm not too concerned about it ( although I think the proof might be a bit twisted or long ) I'm just concerned about the difference of answers up there, any ideas? thanks

 

[Dick]

Homework Statement

of $$f(x) = \sum$$ | x - a_i |
( i = 1 to n )

where
a_1 < a_2 < ... < a_n

The Attempt at a Solution

I believe I have proven that if n is odd then the minimum is as ceiling(n/2) or (n+1)/2. The book says (n-1)/2 though, but I think it's wrong.. if you actually tried an example , f( (n+1)/2 ) < f ((n-1)/2 ). take n = 5 and a_i's = 1,2,3,4,5 for example
Also, for my even case, I have that the minimum occurs at both n/2 and n/2 + 1. Roughly speaking, if you introduce a new point that's mid( n/2 , n/2 + 1 ) then we have an odd case and the minimum as I've shown before will be the most middle point, mid( n/2 , n/2 + 1 ) .. et c I'm fairly sure that I have it right so I'm not too concerned about it ( although I think the proof might be a bit twisted or long ) I'm just concerned about the difference of answers up there, any ideas? thanks

Are you sure you've stated that correctly? If n=2 then the minimum of f(x) is |a_1-a_2| isn't it? It has that value for any x in [a_1,a_2]. Why would it be a function only of n?

 

[holezch]

oops, I wrote my answer incorrectly, the minimum is a_n+1/2 .. etc all the n's I wrote above are are a_n's
sorry I will edit it
so if n = 2 then f ( a_1 ) = f ( a_(n/2) ) = f ( a_( n/2 + 1 ) ) = f ( a_ 2 ) are the minimums

 

[Dick]

oops, I wrote my answer incorrectly, the minimum is a_n+1/2 .. etc all the n's I wrote above are are a_n's
sorry I will edit it
so if n = 2 then f ( a_1 ) = f ( a_(n/2) ) = f ( a_( n/2 + 1 ) ) = f ( a_ 2 ) are the minimums

Look the derivative of f(x) (it's only defined for x not one of the a_i, but that's not really a problem, you can tell me how to work around that). The derivative of |x-a_i| is +1 if x>a_i and -1 if x<a_i. That means that that derivative of f(x) in the even case is zero as long as you have an equal number of a_i above and below x. In the odd case, sure, I think the minimum for n=5 must be at a_3. Which makes it a_{(n+1)/2}.