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

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

Условие

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

  1. отрезки [latex]AB[/latex] и [latex]CD[/latex]
  2. [latex]AB[/latex] и [latex]BC[/latex].

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

Решение

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

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

    рисунок2

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

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

    рис1

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

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

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

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

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

  3. рисунок4

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