Find a point that minimizes the sum of the distances to N given points on a number line.
Consider moving the point. If the point were to one side or the other of all N points, the sum of the distances could be decreased by moving closer; so the sought point must be located within the group of N points.
When the moving point is between two points, its motion increases the distance from one at the same speed as it's decreasing the distance from the other. So if there are more points to one side than the other then there are some sets of points matched left and right, but others on one side (say the right) that are not matched on the left. As mentioned, the ones that are matched left-right are a wash and the motion doesn't affect this component of the sum. But going toward the side with more points (unmatched points) will decrease the sum.
So the minimum is achieved when the imbalance is removed: If there are an even number of points (N is even), the chosen point can be anywhere between the two given points in the middle; if there are an odd number of points given, the new point must coincide with the middle point.
Posted by Charlie
on 2014-10-10 10:06:24