Puzzle: Minimum total distance to few points on the same straight line

Question

You have 9 friends living on a straight street in houses: A,B,C,..,H,I

The distance from the beginnig of the street(from the left) for each house is: A– 1.1 km B – 2.3 km C – 3.0 km D – 4.2 km E – 5.1 km F – 6.3 km G – 13.4 km H – 19.1 km I – 27.5 km

You would like to buy a house at point X that: dist(A,X) + dist(B,X) + … + dist(I,X) is minimum possible value.

I need to find X. I could do it by java program but it will not give precise answer.

Predicted solution: In my opinion X is center of mass(centroid) for points A,B,C,...,H,I which is just average and it is true because of center of mass' definition:

The center of mass is the unique point at the center of a distribution of mass in space that has the property that the weighted position vectors relative to this point sum to zero. In analogy to statistics, the center of mass is the mean location of a distribution of mass in space.

Am I right?

Answer 1

You are looking for global minima for $|x-a_1|+|x-a_2|+|x-a_3|+...|x-a_9|$. Clearly, this will lie on the middle,i.e. $a_5$.

A graph for smaller case would make it clear :

Graph is for $|x-1|+|x-2|+|x-5|$

You can prove it by making cases for $x$ and then writing the expression as a linear one. You will see that it is decreasing till middle one and then increasing.

What you have have found is minima of $|x-a_1+x-a_2+...x-a_9|$ because the centre of mass uses displacement, not distance.

Answer 2

If you stand between two friends so that there are $k$ of your friends to the left and $n-k$ to the right, then moving one unit to the right changes the total distance by $k-(n-k)=2k-n$; and moving to the left accordingly changes it by $n-2k$. One of these is an improvement unless $n=2k$

Similarly, if you stand at the $k$th friend, there are $k-1$ to the left, $n-k$ to the right. Moving a unit to the right changes the total by $k-(n-k)=2k-n$, and moving to the left changes by $(n-k+1)-k=n-2k+1$. One of these is an improvement unless we have $2k\ge n$ and $n\ge 2k-1$ at the same time.

At the optimum (which exists by contnuity), no such small moves can improve the result. Therefore the optimum is

• either at any point between the $\frac n2$th and the $(\frac n2+1)$ friend (including both end points) if $n$ is even
• exactly at the $\frac{n+1}2$th friend if $n$ is odd

Answer 3

The center of mass $\mu:={1\over n}\sum_{k=1}^n a_k$ minimizes the sum of the squared distances, i.e., the quantity $V(x):=\sum_{k=1}^n |x-a_k|^2$.

When you want to minimize the quantity $D(x):=\sum_{k=1}^n |x-a_k|$ then you can argue as follows:

Consider a point $x$ on the line carrying the $a_k$. When there are less points $a_k$ to the left of $x$ than there are to the right of $x$ then replacing $x$ by $x+\delta$, $\>\delta>0$, with no $a_k$ between $x$ and $x+\delta$ will decrease $D$, since all distances $|x-a_k|$ change by $\delta$, but a smaller number of them will increase than will decrease.

It follows that in order to minimize $D$ we have to make sure that an equal number of points $a_k$ is to the left and to the right of $x$. In your example this is the case if $X=E$, i.e., if $x$ coincides with the middle $a_k$. When $n=2m$, any point $x\in[a_m,a_{m+1}]$ is o.k.

Answer 4

To minimize the sum of the distances, you want to move in with your friend in house E. If you locate anywhere else, you'll have more friends on one side than on the other (since you have an odd number of friends in all), in which case a tiny step in the more-friends direction will decrease the sum you're trying to minimize.

If the problem had specified an even number of friends, then any point in the (inclusive) interval between the two midmost friends would suffice as a total-distance minimizer.