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.

Solution


|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny

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.


[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Up|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]