10th Putnam 1950

Given n, not necessarily distinct, points P₁, P₂, ... , 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₁| + |PP_n| by placing P between P₁ and P_n. Similarly, we minimise |PP₂| + |PP_n-1| by placing P between P₂ and P_n-1. And so on. But note that if we minimise |PP₂| + |PP_n-1| then we also minimise |PP₁| + |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.

10th Putnam 1950

© John Scholes
jscholes@kalva.demon.co.uk
5 Mar 2002