Давайте я тут такое рассуждение набросаю (не задумываясь о константах — только о порядке величин).
Мы уже знаем, что бесконечно « перещёлкивать » нельзя, потому что при каждом перещёлкивании строго уменьшается сумма длин отрезков. Но напрямую это даст только оценку из количества всевозможных способов проводить отрезки — а это слишком много (даже больше, чем экспонента, это скорее факториал).
Красивый трюк состоит в том, что можно использовать другую (полу)метрику — принимающую целые значения. А именно: всё, что нужно, чтобы при « перещёлкивании » отрезков сумма их длин уменьшалась — это чтобы для любых трёх точек A,B,C, где A и C из наших n, а B — точка пересечения отрезка AC с каким-то ещё таким же отрезком, выполнялось бы
d(A,B)+d(B,C)=d(A,C).
Так вот — давайте рассмотрим множество X, полученное добавлением к исходному множеству вершин множества всевозможных точек пересечения пары отрезков с вершинами оттуда. И для любой прямой L, не проходящей через точки X, рассмотрим полуметрику, различающую только то, в одной ли точки относительно L полуплоскости. А именно,
d_L (A,B)=0, если точки A и B в одной полуплоскости относительно L, и
d_L (A,B)=1, если в разных;
саму прямую L из рассмотрения выбрасываем — нам эта полуметрика понадобится только на X.
Нужному нам « равенству треугольника для трёх точек на одной прямой » она, конечно, удовлетворяет.
А теперь давайте для любой пары вершин A и B рассмотрим пару прямых, получающихся небольшим параллельным сдвигом прямой AB вправо и влево. Это ~n^2 прямых — и давайте сложим все соответствующие d_L!
Получаем полуметрику, принимающую неотрицательные целые значения. При этом при любом перещёлкивании сумма « длин » строго уменьшается (потому что теперь пары относительно сразу многих прямых оказываются в одной полуплоскости, а были в разных), а исходное значение не больше, чем
~n (пар вершин)* n^2 (складываемых полуметрик),
и это как раз порядка n^3. Вот и получается не больше cn^3 перещёлкиваний!
Post #4271
2.13K
Математические байки В качестве ответвления — коллеги показали задачу C7 из шорт-листа IMO-2014, где оценивается, сколько (в аналогичной ситуации) « перещёлкиваний » может потребоваться. И оценка тут кубическая по количеству точек, с изящным рассуждением.