Задача из журнала «Квант» (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$; сложив их, получим (*)).

   

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

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

   

   Приведём идею другого решения, дающего значительно лучшую оценку. Рассмотрим произвольное разбиение $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. Приведём пример, показывающий, что для операции «типа 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$.



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