Условие
На окружности отметили 4n точек и окрасили их
через одну в красный и синий цвета. Точки каждого цвета
разбили на пары, а точки каждой пары соединили отрезками
того же цвета. Докажите, что если никакие три отрезка не
пересекаются в одной точке, то найдется по крайней мере n
точек пересечения красных отрезков с синими.
Решение
Если AC и BD — пересекающиеся красные отрезки, то
число точек пересечения любой прямой с отрезками AB и CD не
превосходит числа точек пересечения этой прямой с отрезками AC
и BD. Поэтому, заменив красные отрезки AC и BD на отрезки
AB и CD, мы не увеличим число точек пересечения красных отрезков
с синими, а число точек пересечения красных отрезков с красными
уменьшим, так как исчезнет точка пересечения AC и BD. После
нескольких таких операций все красные отрезки станут непересекающимися,
и нам остается доказать, что в этом случае число точек
пересечения красных отрезков с синими не меньше n. Рассмотрим
произвольный красный отрезок. Так как другие красные отрезки
его не пересекают, то по обе стороны от него лежит четное число
красных точек, т. е. нечетное число синих точек. Следовательно,
найдется синий отрезок, пересекающий данный красный отрезок.
Поэтому числе точек пересечения красных отрезков с синими не
меньше числа красных отрезков, т. е. не меньше n.
Источники и прецеденты использования
