# Difference between revisions of "2020 IMO Problems/Problem 6"

Etmetalakret (talk | contribs) |
|||

Line 1: | Line 1: | ||

− | Problem | + | == Problem == |

− | + | Prove that there exists a positive constant <math>c</math> such that the following statement is true: | |

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | |||

− | + | Consider an integer <math>n > 1</math>, and a set <math>S</math> of n points in the plane such that the distance between any two different points in <math>S</math> is at least <math>1</math>. It follows that there is a line <math>\ell</math> separating <math>S</math> such that the distance from any point of <math>S</math> to <math>\ell</math> is at least <math>cn^{- \frac{1}{3}}</math>. | |

+ | |||

+ | (A line <math>\ell</math> separates a set of points <math>S</math> if some segment joining two points in <math>S</math> crosses <math>\ell</math>.) | ||

+ | |||

+ | ''Note''. Weaker results with <math>cn^{- \frac{1}{3}}</math> replaced by <math>cn^{- \alpha}</math> may be awarded points depending on the value | ||

+ | of the constant <math>\alpha > \frac{1}{3}</math>. | ||

+ | |||

+ | == Solution == | ||

+ | |||

+ | For any unit vector <math>v</math>, let <math>a_v=\min_{p\in S} p \cdot v</math> and <math>b_v = \max_{p\in S} p\cdot v</math>. If <math>b_v - a_v\geq n^{2/3}</math> then we can find a line <math>\ell</math> perpendicular to <math>v</math> such that <math>\ell</math> separates <math>S</math>, and any point in <math>S</math> is at least <math>\Omega(n^{2/3}/n) = \Omega(n^{-1/3})</math> away from <math>\ell</math>. | ||

Suppose there is no such direction <math>v</math>, then <math>S</math> is contained in a box with side length <math>n^{2/3}</math> by considering the direction of <math>(1, 0)</math> and <math>(0, 1)</math>, respectively. Hence, <math>S</math> is contained in a disk with radius <math>n^{2/3}</math>. Now suppose that <math>D</math> is the disk with the minimum radius, say <math>r</math>, which contains <math>S</math>. Then, <math>r=O(n^{2/3})</math>. Since the distance between any two points in <math>S</math> is at least <math>1</math>, <math>r=\Omega(\sqrt{n})</math> too. | Suppose there is no such direction <math>v</math>, then <math>S</math> is contained in a box with side length <math>n^{2/3}</math> by considering the direction of <math>(1, 0)</math> and <math>(0, 1)</math>, respectively. Hence, <math>S</math> is contained in a disk with radius <math>n^{2/3}</math>. Now suppose that <math>D</math> is the disk with the minimum radius, say <math>r</math>, which contains <math>S</math>. Then, <math>r=O(n^{2/3})</math>. Since the distance between any two points in <math>S</math> is at least <math>1</math>, <math>r=\Omega(\sqrt{n})</math> too. |

## Revision as of 11:27, 14 May 2021

## Problem

Prove that there exists a positive constant such that the following statement is true:

Consider an integer , and a set of n points in the plane such that the distance between any two different points in is at least . It follows that there is a line separating such that the distance from any point of to is at least .

(A line separates a set of points if some segment joining two points in crosses .)

*Note*. Weaker results with replaced by may be awarded points depending on the value
of the constant .

## Solution

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.

## Video solution

https://www.youtube.com/watch?v=dTqwOoSfaAA [video covers all day 2 problems]