Условие
На плоскости дано n точек, никакие три из которых
не лежат на одной прямой. Докажите, что их можно обозначить
A
1,A
2,...,A
n
в таком порядке, чтобы замкнутая ломаная
A
1A
2...A
n была
несамопересекающейся.
Подсказка
Соедините точки замкнутой ломаной сначала в каком-нибудь порядке,
а затем в случае, если найдутся самопересечения, замените пару
пересекающихся звеньев на пару непересекающихся.
Решение
Обозначим точки A
1,A
2,...,A
n
сначала в каком-нибудь произвольном порядке.
Если замкнутая ломаная A
1A
2...A
n
не имеет самопересечений, то условие задачи выполнено.
Пусть найдутся два пересекающихся звена, пусть для определенности,
это звенья A
1A
2 и
A
kA
k+1. Заменим
эту пару звеньев на звенья A
1A
k
и A
2A
k+1.
Таким образом, мы получаем новую замкнутую ломаную
A
1A
kA
k-1...A
2A
k+1A
k+2...A
n,
соединяющую данные n точек уже в другом порядке.
Поскольку отрезки A
1A
2 и
A
kA
k+1 пересекаются, точки
A
1,A
k,A
2,A
k+1
образуют выпуклый четырехугольник.
В выпуклом четырехугольнике сумма длин диагоналей больше
суммы длин пары противоположных сторон, поэтому
A
1A
2+A
kA
k+1 >
A
1A
k+A
2A
k+1.
Это означает, что при описанной выше процедуре замены пары звеньев
периметр замкнутой ломаной уменьшается.
Выполняем аналогичным образом замены пар звеньев ломаной пока это
возможно, при этом периметр ломаной уменьшается.
Этот процесс не может продолжаться бесконечно, так как способов
упорядочить n точек - конечное число.
В конечном итоге мы придем к замкнутой ломаной без самопересечений
(иначе можно было бы сделать еще одну замену звеньев и
еще раз уменьшить периметр ломаной).
Источники и прецеденты использования
