On a 2-dimensional plane, 2019 points are given such that, for every 3 points picked, there are 2 points whose distance is smaller than 1.
Is there a circle with radius 1 that can contain at least 1010 of the 2019 points?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Suppose the statement is false. Take any one point P and construct a unit circle C P with center P . By our assumption, C P contains no more than 1009 points, so there are at least 1010 points outside of C P .
Take any three points outside C P , call them A , B and C . Then A P , B P and C P are all greater than 1, so A B , B C and A C must all be less than 1.
If we "push" A , B and C as far apart as possible under this constraint, they will be at the vertices of an equilateral triangle of side length 1 (technically just under 1 but that should not affect the proof.)
Now consider any other point X also outside C P . Since X P is greater than 1, X A , X B and X C must all be less than 1, i.e X must lie in the intersection of the unit circles centered at A , B and C (the shaded portion in the left image below). Since X could be any point outside of C P , this means that all points outside of C P must lie in that intersection. But clearly that intersection can itself be contained within a unit circle, as shown in the right image.
So all points outside of C P must lie within that unit circle, and there are at least 1010 such points.