M927. Замена пересекающихся отрезков

Задача из журнала «Квант» (1985, №10)

Условие

На плоскости дано конечное множество точек, никакие три из которых не лежат на одной прямой. Проведено несколько отрезков с концами в данных точках. Эти отрезки разрешается менять: если какие-то два из них, AC и BD, пересекаются, их можно стереть и провести

  1. отрезки AB и CD
  2. AB и BC.

(Если «новый» отрезок уже проведён, проводить его второй раз не нужно.)
Можно ли после нескольких таких замен (только по правилу 1 или по правилу 2, но не по обоим) вернуться к исходному набору отрезков?

Решение

  1. Докажем, что через конечное число операций «типа 1» — замены пересекающихся AB и CD — мы придём к конфигурации, в которой уже не будет пересекающихся отрезков.

    Рассмотрим сумму s длин всех отрезков конфигурации. При каждой операции «типа 1» она уменьшается:
    AB + CD < AC + BD (*)
    (для треугольников APB и CPD, где P — точка пересечения AC и BD — рис. 1, выполнены неравенства AB < AP + PB и CD < CP + PD; сложив их, получим (*)).

    рисунок2

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

    Это решение даёт очень грубую верхнюю оценку для максимального количества T_n операций, которое может быть проделано с конфигурацией на n точках — можно сказать лишь что оно меньше числа всех конфигураций, то есть 2^{n\cdot(n-1)/2}, n\cdot(n-1)/2 — это число различных отрезков с концами в данных n точках.

    рис1

    Приведём идею другого решения, дающего значительно лучшую оценку. Рассмотрим произвольное разбиение f данных точек на два непустых множества, каждое из которых лежит целиком по одну сторону от некоторой прямой l. Таких прямых для данного разбиения, конечно, бесконечно много, но одну из них всегда можно получить, повернув по часовой стрелке прямую, соединяющую две какие-либо точки A и B на очень маленький угол вокруг середины отрезка AB (рис. 2); эту прямую обозначим l_i. Число прямых l_i, и значит, что число рассматриваемых «выпуклых» разбиений не превосходит числа пар точек n\cdot(n-1)/2.

    Назовём балансом конфигурации суммарное число b пересечений её отрезков со всеми прямыми l_i; ясно, что 0 \le b \le (n\cdot(n-1)/2)^2. При операции типа 1 число пересечений любой прямой l_i с отрезками конфигурации не увеличивается, а по крайней мере для одной прямой оно уменьшается на 2. Следовательно, T_n \le n^2 \cdot (n-1)^2 / 8. Интересно было бы получить ещё более точную оценку для T_n.

  2. рисунок1Приведём пример, показывающий, что для операции «типа 2» — замены пересекающихся отрезков AC и BD не имеющих общий конец AB и BC — процесс может «зациклиться» и тем самым продолжаться неограниченно. Расположим 18 точек в вершинах правильного 18-угольника и обозначим через D(k, l) конфигурацию из 36 отрезков, в которой каждая из 18 точек соединена k-й и l-й от неё по счёту.

    Чтобы пройти за 54 операции путь D(4, 8) \to D(5, 9) \to D(6, 7) \to D(4, 8) (рис. 3), достаточно каждую из операций, изображенных на рисунке 4, проделать по 18 раз (поворачивая картинку каждый раз на 20^{\circ}).

    По-видимому, существуют и примеры с существенно меньшим числом точек n и длинной цикла T, чем n = 18 и T = 54.

  3. рисунок4

    Н.Б. Васильев, В.Е. Колосов

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *