Условие
На плоскости даны
n красных и
n синих точек,
никакие три из которых не лежат на одной прямой. Докажите,
что можно провести
n отрезков с разноцветными концами, не имеющих
общих точек.
Решение
Рассмотрим все разбиения данных точек на пары разноцветных
точек. Этих разбиений конечное число, поэтому найдется разбиение, для
которого сумма длин отрезков, заданных парами точек разбиения,
наименьшая. Покажем, что тогда эти отрезки не будут пересекаться. В
самом деле, если бы два отрезка пересекались, то мы смогли бы выбрать
разбиение с меньшей суммой длин отрезков, заменив диагонали выпуклого
четырехугольника на его противоположные стороны (рис.).
Источники и прецеденты использования
