Условие
Какое наименьшее число точек достаточно отметить
внутри выпуклого
n-угольника, чтобы внутри любого треугольника
с вершинами в вершинах
n-угольника содержалась
хотя бы одна отмеченная точка?
Решение
Так как диагонали, выходящие из одной вершины, делят
n-угольник на
n - 2 треугольника,
n-2 точки необходимы.
Из рис. можно понять, как обойтись
n - 2 точками: достаточно
отметить по одной точке в каждом зачерненном треугольнике.
В самом деле, внутри треугольника
ApAqAr, где
p <
q <
r, всегда
содержится зачерненный треугольник, прилегающий к вершине
Aq.
Источники и прецеденты использования
