|
|
 |
Условие
На плоскости задано n точек, являющихся вершинами выпуклого n-угольника, n > 3. Известно, что существует ровно k равносторонних треугольников со стороной 1, вершины которых – заданные точки.
а) Докажите, что k < 2n/3.
б) Приведите пример конфигурации, для которой k > 0,666n.
Решение
а) Для каждой из данных точек существует проходящая через неё прямая, такая что все другие заданные точки лежат по одну сторону от этой прямой. Это позволяет среди всех единичных треугольников с вершиной в рассматриваемой точке выделить два треугольника – "крайний левый" треугольник и "крайний правый" треугольник (не исключено, что они могут
совпадать). Будем называть эти два единичных треугольника присоединёнными к этой вершине.
Лемма. Каждый единичный треугольник будет присоединённым,
по крайней мере, трижды.
Доказательство. Предположим, что единичный треугольник не
является "крайним левым" для вершины C и не является "крайним
правым" для вершины B (см. рис.).
Тогда на дугах AB1 и AC1 обязательно будут заданные точки. Но эти точки вместе с точками A, B и C не образуют выпуклую оболочку. Поэтому этот треугольник будет
присоединённым одним из двух выше указанных способов. Значит, он будет "крайним левым" для вершины C или "крайним правым" для вершины B. Аналогично, он будет "крайним левым" для вершины A или "крайним правым" для вершины C, а также, он будет "крайним левым" для вершины B или "крайним правым" для вершины A. А это значит, что он будет присоединённым по крайней мере трижды.
Предположим теперь, что для заданных точек существует k единичных треугольников. Поскольку для каждой из n точек существует максимум два присоединённых треугольника, то 2n – это наибольшее количество всех возможных присоединений. Так как каждый единичный треугольник будет присоединённым, по крайней мере, трижды, то 3k – это наименьшее количество из всех возможных присоединений. Таким образом, 3k ≤ 2n.
б) Рассмотрим ромб, который состоит из двух правильных треугольников, и будем поворачивать его на очень "маленькие" углы вокруг одной из его тупых вершин так, что в результате получим m ромбов.
Если все углы поворота меньше π/3, то все вершины наших ромбов будут вершинами выпуклого многоугольника. При этом
n = 3m + 1, k = 2m, и, если m достаточно велико, k > 0,666n.
