Given n, not necessarily distinct, points P1, P2, ... , Pn on a line. Find the point P on the line to minimize ∑ |PPi|.
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 |PP1| + |PPn| by placing P between P1 and Pn. Similarly, we minimise |PP2| + |PPn-1| by placing P between P2 and Pn-1. And so on. But note that if we minimise |PP2| + |PPn-1| then we also minimise |PP1| + |PPn|. 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.
10th Putnam 1950
© John Scholes
5 Mar 2002