Задача о точках и отрезках

[Юстас]

На плоскости имеются N точек и N-2 непересекающихся отрезка. Всегда ли найдутся 2 точки, которые "видят" друг друга, то есть отрезок, их соединяющий, не пересекается ни с одним из данных N-2?

[Руст]

Да всегда. Докажем по индукции, что для разделения N точек на невидимые друг для друга точки необходимо N-1 отрезков. Случаи N=1 и 2 очевидны. Тогда взяв один отрезок, получаем разделение множества на два подмножества (как прямой). При этом в лучшем случае две точки из разных подмножеств невидимы. Если подмножества имеют K и N-K элементов, по индукции требуется как минимум (K-1)+(N-K-1)+1=N-1 прямых для полного разделения.

[evgeny]

Это не совсем так.
На сколько я понимаю Вы в Ваших рассуждениях рассматриваете прямые вместо отрезков,
а для для прямых это уже неверно
(т.к. $n$ прямых могут разделить плоскость на $\frac{n^2+n+2}{2} частей$.
Т.е. если разбивать на множества в точности как Вы указали (разрезать по прямой),
то последуюшие отрезки могут разделять точки сразу в обоих подмножествах
(и отрезки при этом не пересекаются)

[Юстас]

Рассуждение Руста верное, просто необходимо показать, что всегда можно так изменить конфигурацию точек и отрезков, что будет хотя бы один "максимально эффективный", то есть разделяющий множество точек на два невидимых, отрезок, при этом общее количество отрезков не изменится. Это почти очевидно.