Задача
На плоскости даны n красных и n синих точек, никакие три из которых не лежат на одной прямой. Докажите, что можно провести n отрезков с разноцветными концами, не имеющих общих точек.
Решение
Рассмотрим все разбиения данных точек на пары разноцветных. Этих разбиений конечное число, поэтому найдётся разбиение (назовем его минимальным), для которого сумма длин отрезков, заданных парами точек этого разбиения, наименьшая. Покажем, что тогда эти отрезки не будут пересекаться.
В самом деле, если бы два отрезка K1C1 и K2C2 с разноцветными концами пересеклись (будем обозначать красные точки буквами K, а синие — C), то мы смогли бы выбрать разбиение с меньшей суммой длин отрезков, заменив диагонали K1C1 и K2C2 выпуклого четырёхугольника K1C2C1K2 на его противоположные стороны K1C2 и K2C1. Тогда
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь