Given n, not necessarily distinct, points P_{1}, P_{2}, ... , P_{n} on a line. Find the point P on the line to minimize ∑ |PP_{i}|.

**Solution**

Assume that the points are in the order given. For two points A and B, |PA| + |PB| = AB for P on the segment AB and |PA| + |PB| > AB for P outside it. Thus we minimise |PP_{1}| + |PP_{n}| by placing P between P_{1} and P_{n}. Similarly, we minimise |PP_{2}| + |PP_{n-1}| by placing P between P_{2} and P_{n-1}. And so on. But note that if we minimise |PP_{2}| + |PP_{n-1}| then we also minimise |PP_{1}| + |PP_{n}|. Thus for n odd we must take P to be the central point, for n even we can take P to be any point on the segment between the two central points.

© John Scholes

jscholes@kalva.demon.co.uk

5 Mar 2002