Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How many integral values of $(X,Y)$ are there such $$((|X-L_1|+|Y-M_1|)+(|X-L_2|+|Y-M_2|)+\cdots+(|X-L_n|+|Y-M_n|))$$ is minimized?

$10^{-6} < X < 10^6$

$10^{-6} < Y < 10^6$


share|improve this question
4  
Zero percent accept rate? Do you know about accepting answers to your questions, and why that's a good thing to do? –  Gerry Myerson May 3 '12 at 5:56
2  
Your link is to an image that is no longer available, and links are discouraged for this reason. Please restore the question to this site. –  Ross Millikan May 3 '12 at 13:24
1  
-1: There is no question. –  spohreis May 3 '12 at 13:43
    
possible duplicate of To find the number of points on a 2D grid? (which was also posted by a user with 0% accept rate) –  joriki May 16 '12 at 8:15

1 Answer 1

up vote 2 down vote accepted

You want X to be a median of the L's and Y to be a median of the M's. For an even count, this can be any value between the central two. This is stated, but not proved, in Wikipedia's article on the median under an optimality property.

To see why the median is the right answer, if X is greater than all the L's and decreases by 1, the total will decrease by the number of L's. The total will still decrease with decreasing X until there are as many L's above as below X. That is the definition of median.

share|improve this answer
    
When $N$ is odd, there is a unique median, so a unique $X$ and a unique $Y$. –  Gerry Myerson May 3 '12 at 5:56

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.