Условие
Докажите, что при n
3 среди полученных частей
не менее (2n - 2)/3 треугольников.
Решение
Рассмотрим все точки пересечения данных прямых. Докажем,
что эти точки могут лежать по одну сторону не более чем от двух данных
прямых. Предположим, что все точки пересечения лежат по одну сторону
от трех данных прямых. Эти прямые образуют треугольник ABC.
Четвертая прямая не может пересекать только стороны этого
треугольника, т. е. она пересекает хотя бы одно продолжение стороны.
Пусть для определенности она пересекает продолжение стороны AB за
точку B в некоторой точке M. Тогда точки A и M лежат по
разные стороны от прямой BC. Получено противоречие. Поэтому имеются
по крайней мере n - 2 прямые, по обе стороны от которых лежат точки
пересечения.
Если мы выберем в полуплоскости, заданной прямой l, ближайшую к l
точку пересечения, то эта точка будет вершиной треугольника,
прилегающего к прямой l. Таким образом, имеется не менее n - 2
прямых, к которым прилегает по крайней мере по два треугольника,
и две прямые, к каждой из которых прилегает хотя бы один
треугольник. Так как каждый треугольник прилегает ровно к трем
прямым, то треугольников не менее
(2(n - 2) + 2)/3.
Источники и прецеденты использования
