Question

На плоскости дано бесконечное множество точек S, при этом в любом квадрате 1 × 1 лежит конечное число точек из множества S. Докажите, что найдутся две разные точки A и B из S такие, что для любой другой точки X из S выполняется: |XA|,\;|XB| ≥ 0,999|AB|.

Answer 1

Ответ:

Докажем утверждение задачи от противного.

Можно предположить, что для любых двух разных точек A и B из S найдется отличная от них точка X из S такая, что либо XA < 0,999AB, либо XB < 0,999AB.

Переформулируем вышеприведенное утверждение: для любого отрезка I с концами в S и длиной l найдется отрезок I′ с концами в S длины не более 0,999l, один из концов которого совпадает с некоторым концом I.

Или, иначе говоря, I′ пересекает I.

Возьмем теперь первый отрезок I1 длины l и будем брать отрезки I2, I3, …так, что Ik + 1 пересекается с Ik и |Ik + 1| < 0,999|Ik|.

Все эти отрезки имеют концы в S. Ломаная не короче отрезка, соединяющего ее концы, поэтому расстояние от любого конца Ik до любого конца I1 не превосходит

Следовательно, в квадрате 2000l × 2000l с центром в любом из концов I1 лежит бесконечное число точек S.

Но из условия следует конечность их числа в любом квадрате.

Полученное противоречие завершает доказательство.

Объяснение:

Answer 2

Для доказательства этого утверждения воспользуемся методом доказательства от противного. Предположим, что такие точки A и B не существуют, то есть для любой пары различных точек A и B из S найдется точка X из S, для которой выполнено либо |XA| < 0.999|AB|, либо |XB| < 0.999|AB|.

Пусть S1 обозначает множество всех точек из S, которые не соответствуют условию |XA| < 0.999|AB| для некоторых A и B из S, и S2 обозначает множество всех точек из S, которые не соответствуют условию |XB| < 0.999|AB| для некоторых A и B из S. То есть S1 содержит точки, для которых не выполняется первое условие, и S2 содержит точки, для которых не выполняется второе условие.

Так как для каждой пары точек A и B из S найдется точка, которая не соответствует одному из условий, то множество S1 и множество S2 покрывают все точки из S, и S можно представить в виде объединения S1 и S2: S = S1 ∪ S2.

Теперь рассмотрим квадрат 1 × 1. По условию, внутри него лежит конечное число точек из множества S. Из этого следует, что внутри этого квадрата должно лежать конечное число точек из множества S1 (иначе можно было бы выбрать квадраты, содержащие только точки из S1 и получить бесконечное количество точек внутри каждого такого квадрата, что противоречит условию задачи).

Аналогично, внутри квадрата 1 × 1 должно лежать конечное число точек из множества S2.

Теперь рассмотрим квадрат со сторонами, параллельными осям координат, и вершинами в точках (0, 0), (1, 0), (0, 1) и (1, 1). Внутри этого квадрата лежит конечное число точек из множества S1 и конечное число точек из множества S2.

Однако, так как квадрат 1 × 1 разбивается на 4 квадрата со сторонами 0.5 × 0.5, то по принципу Дирихле в одном из этих 0.5 × 0.5 квадратов должно лежать бесконечное число точек из множества S1 или бесконечное число точек из множества S2 (или даже из обоих).

Пусть, например, в 0.5 × 0.5 квадрате лежит бесконечное число точек из множества S1. Тогда мы можем проделать тот же самый процесс с этим квадратом: разбить его на 4 квадрата 0.25 × 0.25 и найти в одном из них квадрат, в котором лежит бесконечное число точек из множества S1.

Продолжая этот процесс бесконечное число раз, мы получим последовательность квадратов с уменьшающимся размером, в каждом из которых лежит бесконечное число точек из множества S1. Это приводит к противоречию, так как множество S1 состоит из точек, для которых не выполняется условие |XA| < 0.999|AB| для некоторых A и B из S, и внутри каждого квадрата размером 1 × 1 можно выбрать лишь конечное число точек, не соответствующих этому условию.

Следовательно, наше предположение о том, что не существует точек A и B из S, для которых для любой другой точки X из S выполняется |XA|, |XB| ≥ 0,999|AB|, было неверным. Такие точки A и B действительно существуют.