Общая точка, прямая, покрытие. Теорема Хелли

Введем систему координат с осью параллельной данным отрезкам. Для каждого отрезка рассмотрим множество всех таких точек что прямая его пересекает. Достаточно проверить, что эти множества выпуклые, и применить к ним теорему Хелли. Для отрезка с концами и рассматриваемое множество является полосой, заключенной между параллельными прямыми и

Поскольку у параллелепипедов ребра соответственно параллельны, мы можем ввести декартову систему координат, направив оси вдоль трех ребер, смежных с одной вершиной (которая станет началом координат) выбранного параллелепипеда. В этой системе координат ребра всех параллелепипедов будут параллельны осям. Спроектировав на ось Ох данный -ый параллелепипед получим отрезок, который обозначим Любая пара таких отрезков имеет непустое пересечение (в противном случае соответствующая пара параллелепипедов не пересекается).

Таким образом, приходим к такой задаче: на числовой прямой есть попарно пересекающиеся отрезки и требуется доказать, что у них имеется общая точка. Опытные олимпиадники могут сразу сослаться на теорему Хелли. Мы же приведём её доказательство, чтобы не оставлять у неопытных читателей чувство неловкости.

Пусть – наибольшее значение среди левых концов отрезков, т.е. и аналогично, пусть — наименьшее значение среди правых концов отрезков. Тогда так как в противном случае для некоторых и а значит, -ый и -ый отрезки не пересекаются. Отсюда следует, что любая точка отрезка будет общей для всех наших отрезков. Итак, пусть точка принадлежит проекциям на ось Ох всех параллелепипедов. Точно так же мы можем найти общие точки и проекций на оси Oy и Oz. Тогда точка с координатами будет принадлежать всем параллелепипедам.

(a) Рассмотрим прямую, перпендикулярную нашему направлению. Спроецируем ортогонально все наши фигуры на эту прямую. Заметим, что проекция каждой нашей фигуры является интервалом (возможно бесконечный, также допускаются полуоткрытые или открытые интервалы). Заметим, что теорема Хелли для прямой работает также и для наших проекций (все рассуждения аналогичны). Тогда все наши проекции имеют общую точку Восстановив перпендикуляр к точке получем прямую нужного направления, пересекающую все наши фигуры.

(b) Рассмотрим фиксированную точку Выберем произвольную прямую, не проходящую через Спроецируем на нее через точку все наши фигуры. Получим ту же конструкцию, что и в предыдущем пункте. Опять же по теореме Хелли для прямой все наши проекции имеют общею точку Тогда прямая — искомая.

Рассмотрим все пятиугольники, образованные пятерками соседних вершин. Заметим, что все они выпуклые. Заметим, что любые три пятиугольника суммарно покрывают вершины исходного семиугольника раз. Тогда по принципу Дирихле какая-то вершина покрыта хотя бы раза. То есть мы показали, что любые пятиугольника имеют общую точку. Тогда по теореме Хелли есть точка, принадлежащая всем пятиугольникам. Предположим, что она лежит на границе одного из пятиугольников. Такое возможно, только если эта точка лежит на некоторых диагоналях семиугольника. Немного подвинем ее, чтобы она попала строго вовнутрь всех пятиугольников. Теперь мы нашли точку, которая не лежит ни в одном из четырехугольников (так как она лежит в их дополнениях).

Для каждой точки из данных рассмотрим круг с центром в и радиусом Докажем, что любые три таких круга имеют общую точку. Рассмотрим три точки и соответствующие им круги. Предположим, что они не имеют общей точки. Тогда начнем удалять точку от точки по прямой пока расстояние между какими-то двумя точками не станет равным Заметим, что от такого действия общая точка появится не может, поскольку не изменяется, а только уменьшается (является подмножеством исходного). Таким образом мы добились того, что одна из сторон или стала равна Не нарушая общности, пусть Далее аналогично двигаем точку от точки и получаем, что уже две стороны треугольника равны Пусть Теперь вращаем точку относительно так, чтобы она стала как можно дальше от Таким образом получим, что можно считать, что треугольник — равносторонний. Но в этом случае наши три круга имеют общую точку. Ей будет центр описанной окружности треугольника Тогда и в исходном треугольнике круги имели общую точку — противоречие.

Значит, любые три круга действительно пересекаются в одной точке. Тогда по теореме Хелли все круги имеют общую точку Но тогда все наши точки лежат в круге с центром и радиусом что и требовалось.

Заключим все прямоугольники в один большой квадрат со сторонами параллельными осям координат. Выберем во второй четверти точку лежащую выше и левее всего квадрата. Тогда легко понять, что через нее не проходит ни одна восходящая прямая, пересекающая хотя бы один из наших прямоугольников. Теперь каждой восходящей прямой будем сопоставлять точку, являющуюся полюсом этой прямой относительно единичной окружности с центром в Посмотрим на полюсы множества восходящих прямых, пересекающих фиксированный прямоугольник. Покажем, что оно выпукло. Рассмотрим два полюса и Тогда поляра любой точки на отрезке это восходящая прямая, проходящая между полярами и Тогда легко понять, что она тоже будет пересекать выбранный прямоугольник. Таким образом, выпуклость мы показали. С другой стороны мы знаем, что для любых прямоугольников их множества полюсов имеют общую точку. Тогда по теореме Хелли все множества полюсов имеют общую точку Поляра точки будет пересекать все прямоугольники.

Заметим, что если какие-то три точки встретились вместе только один раз, то и все остальные точки также должны были в этот момент времени с ними встретиться. Если же одни и те же три точки встретились хотя бы два раза, то они будут встречаться бесконечно много раз, причем времена их встреч образуют арифметическую прогрессию. Поэтому докажем следующую лемму, откуда будет следовать утверждение задачи.
Лемма
Пусть — арифметические прогрессии с натуральными разностями причем любые две из них пересекаются. Тогда найдется число, принадлежащее множеству значений всех этих прогрессий.

Доказательство
Индукция по числу прогрессий. База для прогрессий очевидна. Докажем переход от к Не умаляя общности (и по индукционному предположению) можно считать, что прогрессии начинаются с нуля. Пусть Поскольку прогрессии имеют общую точку, мы можем считать, что первый член прогрессии равен (где — некоторое натуральное число). А поскольку прогрессии и тоже пресекаются, прогрессия должна содержать число вида . Если то мы нашли общую точку всех прогрессий. В противном случае прогрессия содержит все числа вида

По китайской теореме об остатках существует число которое делится на НОД и имеет остаток 1 при делении на
НОД При таком соответствующий член прогрессии делится и на и на т.е. принадлежит множеству значений всех прогрессий.
Покажем, как из леммы следует утверждение задачи. Зафиксируем пару точек и и запустим отсчет времени с момента какой-нибудь их встречи. Пусть в следующий раз они встретились через секунд, тогда далее все их встречи будут происходить в моменты времени где Для каждой точки моменты ее встреч с парой образуют арифметическую прогрессию (здесь — момент их первой совместной встречи, — интервал между двумя последовательными встречами, ). По условию точки и встретятся вместе, поэтому прогрессии и пересекаются для любой пары точек и Тогда, согласно лемме, у всех таких прогрессий есть общая точка Значит, в момент времени все точки встретятся вместе.