2020 IMO Problems/Problem 6
Problem 6. Prove that there exists a positive constant c such that the following statement is true: Consider an integer n > 1, and a set S of n points in the plane such that the distance between any two different points in S is at least 1. It follows that there is a line ℓ separating S such that the distance from any point of S to ℓ is at least cn^(−1/3) . (A line ℓ separates a set of points S if some segment joining two points in S crosses ℓ.) Note. Weaker results with cn^(−1/3) replaced by cn^−α may be awarded points depending on the value of the constant α > 1/3.
Proof. For any unit vector , let and . If then we can find a line perpendicular to such that separates , and any point in is at least away from .
Suppose there is no such direction , then is contained in a box with side length by considering the direction of and , respectively. Hence, is contained in a disk with radius . Now suppose that is the disk with the minimum radius, say , which contains . Then, . Since the distance between any two points in is at least , too.
Let be any point in on the boundary of . Let be the line tangent to at , and the line obtained by translating by distance towards the inside of . Let be the region sandwiched by and . It is easy to show that both the area and the perimeter of is bounded by (since ). Hence, there can only be points in , by that any two points in are distance apart. Since the width of is , there must exist a line parallel to such that separates , and any point in is at least away from . Q.E.D.
Note. One can also show that is best possible.
https://www.youtube.com/watch?v=dTqwOoSfaAA [video covers all day 2 problems]