|
|
 |
Условие
На плоскости проведены n прямых, среди которых нет параллельных. Никакие три из них не пересекаются в одной точке. Докажите, что существует такая n-звенная несамопересекающаяся ломаная A0A1A2...An, что на каждой из n прямых лежит ровно по одному звену этой ломаной.
Решение
Докажем по индукции более сильный факт: пусть A0 – произвольная точка на одной из данных прямых, через которую
не проходит ни одна из остальных прямых; тогда существует требуемая ломаная, начинающаяся с A0.
База. При n = 1 ломаная (из одного отрезка) строится тривиально.
Шаг индукции. Пусть l1, ..., ln – данные прямые, A0 лежит на ln, A1 – ближайшая к A0 точка пересечения ln с остальными прямыми (если ближайших точек две, выберем любую из них). Можно считать, что A1 лежит на ln–1.
По предположению индукции существует несамопересекающаяся ломаная A1A2...An, начинающаяся с A1 и содержащая по одному звену на каждой из прямых l1, ..., ln–1. Тогда
A0A1...An – требуемая ломаная.
