3582. На плоскости даны n
красных и n
синих точек, никакие три из которых не лежат на одной прямой. Докажите, что можно провести n
отрезков с разноцветными концами, не имеющих общих точек.
Указание. Если ABCD
— выпуклый четырёхугольник, то BC+AD\lt AC+BD
.
Решение. Рассмотрим все разбиения данных точек на пары разноцветных. Этих разбиений конечное число, поэтому найдётся разбиение (назовём его минимальным), для которого сумма длин отрезков, заданных парами точек этого разбиения, наименьшая. Покажем, что тогда эти отрезки не будут пересекаться.
В самом деле, если бы два отрезка K_{1}C_{1}
и K_{2}C_{2}
с разноцветными концами пересеклись (будем обозначать красные точки буквами K
, а синие — C
), то мы смогли бы выбрать разбиение с меньшей суммой длин отрезков, заменив диагонали K_{1}C_{1}
и K_{2}C_{2}
выпуклого четырёхугольника K_{1}C_{2}C_{1}K_{2}
на его противоположные стороны K_{1}C_{2}
и K_{2}C_{1}
. Тогда
K_{1}C_{2}+K_{2}C_{1}\lt K_{1}C_{1}+K_{2}C_{2},
что противоречит выбору минимального разбиения.