Условие
Чему равно наибольшее число вершин невыпуклого
n-угольника, из которых нельзя провести диагональ?
Решение
Докажем сначала, что если
A и
B — соседние вершины
n-угольника, то из
A или из
B можно провести диагональ.
Случай, когда внутренний угол многоугольника при вершине
A
больше
180
o, разобран в решении задачи
22.20, а).
Предположим теперь, что угол при вершине
A меньше
180
o.
Пусть
B и
C — вершины, соседние с
A. Если внутри
треугольника
ABC нет других вершин многоугольника, то
BC —
диагональ, а если
P — ближайшая к
A вершина
многоугольника, лежащая внутри треугольника
ABC, то
AP —
диагональ. Следовательно, число вершин, из которых нельзя провести
диагональ, не превосходит [
n/2] (т. е. целой части числа
n/2).
С другой стороны, существуют
n-угольники, для которых эта оценка
достигается (рис.).
Источники и прецеденты использования
