Advanced book on Mathematics Olympiad

Real Analysis 563

line passing through the origin that is the clockwise rotation oflby 90◦. The origin of
the coordinate system of the plane will also be the origin of the coordinate system onl⊥.
An oriented linelis determined by two parameters: θ, the angle it makes with the
positive side of thex-axis, which should be thought of as a point on the unit circle or an
element of 2 πRZ; andx, the distance fromlto the origin, taken with sign onl⊥. Define
f:( 2 RπZ)×R→R,

f(θ,x)=

∑n

i= 1

dist(Pi,l),

wherelis the line determined by the pair(θ, x). The functionfis continuous and
limx→±∞f(θ,x)=∞for allθ; hencefhas an absolute minimumf(θmin,xmin).
For fixedθ,f(θ,x)is of the form

∑n
i= 1 |x−ai|, which is a piecewise linear convex
function. Herea 1 ≤a 2 ≤ ··· ≤anare a permutation of the coordinates of the projections
ofP 1 ,P 2 ,...,Pnontol⊥. It follows from problem 426 that at the absolute minimum of
f,xmin=an/ 2 + 1 ifnis odd andan/ 2 ≤xmin≤an/ 2 + 1 ifnis even (i.e.,xminis the
median of theai,i= 1 , 2 ,...,n).
If two of the points project atan/ 2 + 1 , we are done. If this is not the case, let
us examine the behavior off in the direction ofθ. By applying a translation and a
rotation of the original coordinate system, we may assume thatai=xi,i= 1 , 2 ,...,n,
xmin=xn/ 2 + 1 =0,yn/ 2 + 1 =0, andθmin=0. Thenf( 0 , 0 )=

∑

i|xi|. If we rotate
the line by an angleθkeeping it through the origin, then for smallθ,

f(θ, 0 )=

∑

i<n/ 2 + 1

(−xicosθ−yisinθ)+

∑

i>n/ 2 + 1

(xicosθ+yisinθ)

=

∑n

i= 1

|xi|cosθ+

∑

i<n/ 2 + 1

(−yi)sinθ+

∑

i>n/ 2 + 1

yisinθ.

Of course, the absolute minimum off must also be an absolute minimum in the first
coordinate, so

∂f

∂θ

( 0 , 0 )=

∑

i<n/ 2 + 1

(−yi)+

∑

i>n/ 2 + 1

yi= 0.

The second partial derivative offwith respect toθat( 0 , 0 )should be positive. But this
derivative is

∂^2 f

∂θ^2

( 0 , 0 )=−

∑n

i= 1

|xi|< 0.

Hence the second derivative test fails, a contradiction. We conclude that the line for
which the minimum is achieved passes through two of the points. It is important to note