Задача 34916

Темы:    [ Комбинаторная геометрия (прочее) ] [ Примеры и контрпримеры. Конструкции ]

Сложность: 3+ Классы: 7,8

Условие

Какое наименьшее число точек достаточно отметить внутри выпуклого n-угольника, чтобы внутри каждого треугольника с вершинами в вершинах этого n-угольника содержалась хотя бы одна отмеченная точка?

Подсказка

Ставьте точки "вблизи" вершин n-угольника.

Решение

  Оценка. Поскольку n-угольник можно разрезать диагоналями на  n – 2  треугольника и в каждом из них должно быть по точке, то необходимо отметить по крайней мере  n – 2  точки.
  Пример. Обозначим вершины n-угольника A₀, A₁, ..., A_n–1. Поставим k-ю точку B_k  (k = 1, 2, ..., n –2)  "вблизи" вершины A_k внутри угла A₀A_kA_n (точнее, в пересечении этого угла и треугольника A_k–1A_kA_k+1). Рассмотрим произвольный треугольник A_iA_kA_j  (i < k < j).  Этот треугольник содержит точку B_k, поскольку угол A_iA_kA_j содержит угол A₀A_kA_n, а диагональ A_k–1A_k+1 пересекает отрезки A_iA_k и A_kA_j.

Ответ

n – 2  точки.

Источники и прецеденты использования

web-сайт

задача