Условие
Внутри квадрата со стороной 1 даны n точек.
Докажите, что:
а) площадь одного из треугольников с вершинами в этих
точках или вершинах квадрата не превосходит
1/(2(n + 1));
б) площадь одного из треугольников с вершинами в этих
точках не превосходит 1/(n - 2).
Решение
а) Пусть
P1,..., Pn — данные точки. Соединим
точку P1 с вершинами квадрата. При этом получится четыре
треугольника. Затем для
k = 2,..., n проделаем следующую операцию.
Если точка Pk лежит строго внутри одного из полученных ранее
треугольников, то соединим ее с вершинами этого треугольника. Если
точка Pk лежит на общей стороне двух треугольников, то соединим ее с
вершинами этих треугольников, противолежащими общей стороне. После
каждой такой операции в обоих случаях число треугольников увеличивается
на два. В результате получится 2(n + 1) треугольников. Сумма площадей
этих треугольников равна 1, поэтому площадь одного из них не
превосходит
1/(2(n + 1)).
б) Рассмотрим наименьший выпуклый многоугольник, содержащий
данные точки. Пусть он имеет k вершин. Если k = n, то
этот k-угольник можно разбить на n - 2 треугольников диагоналями,
выходящими из одной вершины. Если же k < n, то внутри k-угольника
лежит n - k точек и его можно разбить на треугольники способом,
указанным в предыдущей задаче. При этом получится
k + 2(n - k - 1) = 2n - k - 2 треугольников. Так как k < n, то
2n - k - 2 > n - 2.
Сумма площадей треугольников разбиения меньше 1, а их
количество не меньше n - 2, поэтому площадь хотя бы одного из
них не превосходит 1/(n - 2).
Источники и прецеденты использования
