All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Optimal location (Posted on 2014-10-10)
Find a point that minimizes the sum of the distances to N given points on a number line.

 No Solution Yet Submitted by Art M No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution (spoiler) | Comment 1 of 2
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

 Search: Search body:
Forums (0)