Problem:
2015 points are given in a plane such that from any five points we can choose two points with distance less than 1 unit. Prove that 504 of the given points lie on a unit disc.
Solution
Solution:
Start from an arbitrary point and draw a unit disc with center . If all other points belong to this disc then we are done. Otherwise, take any point outside of the disc. Draw a unit disc with center . If two drawn discs cover all 2015 points, by the pigeonhole principle (PHP), one of the discs contains at least 1008 points.
Suppose that there is a point outside of the two drawn discs. Draw a unit disc with center . If three drawn discs cover all 2015 points, by PHP, one of the discs contains at least 672 points.
Finally, if there is a point outside of the three drawn discs, draw a unit disc with center . By the given condition, any other point belongs to one of the four drawn discs. By PHP, one of the discs contains at least 504 points, concluding the solution.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.