|
Given is a planar set of 25 points such that among any three there exists a pair at the distance
less than 1. Prove that there exists a circle of radius 1 that contains at least 13 of the given points.
|

Pick arbitrarily one point A out of the given 25 and consider a circle B(A,1)
centered at A and radius 1. If all the remaining points lie inside B(A,1), there
is nothing to prove - B(A,1) is the circle we've been looking for.
Else, there is a point B that lies outside B(A,1). Let B(B,1) be
a unit circle centered at B. By definition, the distance between A and B exceeds 1. For
any point C, by the given condition, either the distance to A or the distance to B is less then 1. In
other words, each of the remaining points belongs to either B(A,1) or B(B,1).
By the Pigeonhole Principle, at least 13 lie in the same circle.

Copyright © 1996-2008 Alexander Bogomolny
|