Вопрос школьника
На плоскости отметили 25 точек так, что среди любых трёх из них найдутся две точки, расстояние между которыми меньше единицы. Докажите, что существует окружность единичного радиуса, которая содержит не менее 13 данных точек.
Ответ от учителя
Для начала заметим, что если расстояние между двумя точками равно единице, то они не могут быть вместе на окружности единичного радиуса. Также заметим, что если мы возьмем любую точку и проведем окружность единичного радиуса с центром в этой точке, то на этой окружности будет не более 6 точек (это следует из того, что расстояние между любыми двумя точками на окружности единичного радиуса равно единице).
Теперь предположим, что существует окружность единичного радиуса, которая содержит не более 12 точек из нашего множества. Разделим плоскость на 12 секторов, каждый из которых будет иметь центр в центре окружности и угол в 30 градусов. Так как на окружности не может быть более 6 точек, то в каждом секторе будет не более 2 точек из нашего множества.
Теперь рассмотрим любые 3 точки из нашего множества. Пусть они лежат в секторах A, B и C. Если в каждом из этих секторов есть не более 1 точки из нашего множества, то мы можем провести окружности единичного радиуса с центрами в этих точках и заметить, что расстояние между любыми двумя точками на этих окружностях будет меньше единицы, что противоречит условию задачи. Значит, в одном из секторов должно быть не менее 2 точек из нашего множества.
Таким образом, мы доказали, что любые 3 точки из нашего множества должны лежать в одном из 12 секторов. Значит, если мы возьмем любую точку на окружности единичного радиуса и проведем 12 секторов с центрами в этой точке и углами в 30 градусов, то в каждом из этих секторов будет не более 2 точек из нашего множества. Значит, всего на окружности будет не более 24 точек из нашего множества.
Но у нас есть 25 точек в нашем множестве, значит, как минимум одна точка не лежит на окружности единичного радиуса. Проведем окружность единичного радиуса с центром в этой точке. Тогда на этой окружности будет не более 6 точек из нашего множества, а вне этой окружности будет не менее 19 точек. Значит, всего на плоскости будет не менее 25 — 6 = 19 точек из нашего множества, которые лежат вне окружности единичного радиуса.
Теперь рассмотрим любые 13 точек из нашего множества, которые лежат вне окружности единичного радиуса. Расстояние между любыми двумя точками из этого множества больше единицы, значит, они не могут лежать на одной окружности единичного радиуса. Значит, они должны лежать в разных секторах, каждый из которых имеет угол не менее 30 градусов. Но тогда сумма углов в этих секторах будет не менее 390 градусов, что противоречит тому, что сумма углов в любом многоугольнике на плоскости равна 360 градусов.
Таким образом, мы пришли к противоречию, и наше предположение о том, что существует окружность единичного радиуса, которая содержит не более 12 точек из нашего множества, неверно. Значит, существует окружность единичного радиуса, которая содержит не менее 13 точек из нашего множества.
