Условие
На плоскости дано 300 точек, никакие 3
которых не лежат на одной прямой.
Докажите, что существует 100 попарно не пересекающихся
треугольников с вершинами в этих точках.
Подсказка
Рассмотрите проекции данных точек на некоторую прямую.
Решение
Примем за ось Ox некоторую прямую, не перпендикулярную ни одной из
прямых, соединяющих пары данных точек.
Обозначим x-ые координаты данных точек через
x
1, x
2, ... , x
300
в порядке возрастания
(x
1<x
2<...<x
300).
Возьмем первый треугольник с вершинами в
x
1, x
2, x
3,
второй треугольник - с вершинами в
x
4, x
5, x
6, и т.д.,
сотый треугольник - с вершинами в
x
298, x
299, x
300.
Проекции на ось Ox полученных 100 треугольников
не пересекаются. Значит, и сами треугольники не пересекаются.
Источники и прецеденты использования
