Олимпиадная задача по комбинаторной геометрии: точки внутри n-угольник
Задача
Какое наименьшее число точек достаточно отметить внутри выпуклого n-угольника, чтобы внутри каждого треугольника с вершинами в вершинах этого n-угольника содержалась хотя бы одна отмеченная точка?
Решение
Оценка. Поскольку n-угольник можно разрезать диагоналями на n – 2 треугольника и в каждом из них должно быть по точке, то необходимо отметить по крайней мере n – 2 точки.
Пример. Обозначим вершины n-угольника A0, A1, ..., An–1. Поставим k-ю точку Bk (k = 1, 2, ..., n –2) "вблизи" вершины Ak внутри угла A0AkAn (точнее, в пересечении этого угла и треугольника Ak–1AkAk+1). Рассмотрим произвольный треугольник AiAkAj (i < k < j). Этот треугольник содержит точку Bk, поскольку угол AiAkAj содержит угол A0AkAn, а диагональ Ak–1Ak+1 пересекает отрезки AiAk и AkAj.
Ответ
n – 2 точки.
Чтобы оставлять комментарии, войдите или зарегистрируйтесь