Какое наибольшее число вершин, из которых нельзя провести ни одной диагонали (лежащей целиком внутри многоугольника) может иметь невыпуклый $n$—угольник? Решите эту задачу сначала для $n=4$, 5, 6, 7.
Докажем, что число таких вершин не превосходит $\left[\dfrac{n}{2}\right]$. Это сразу вытекает из следующей леммы:
Лемма.Если $A$ и $B$ — соседние вершины невыпуклого многоугольника $M$, то из $A$ или из $B$ можно провести диагональ.
Доказательство. Пусть $B$ и $C$ — вершины многоугольника $M$, соседние с $A$.
Предположим сначала, что $\widehat{BAC}\lt180^\circ$. Если в треугольнике $ABC$ (включая его стороны) нет других вершин многоугольника $M$, то искомая диагональ — $[BC]$. Если же в треугольнике $ABC$ есть другие вершины многоугольника $M$, то выберем среди них вершину $D$, находящуюся на минимальном расстоянии от прямой $l$, проходящей через точку $A$ параллельно $[BC]$. Тогда $[AD]$ — искомая диагональ, поскольку в противном случае отрезок $AD$ пересекала бы какая-то сторона $EF$ многоугольника $M$ (рис. 5), один из концов которой лежал бы ближе к прямой $l$, чем точка $D$, что противоречило бы выбору последней.
Рис. 5Рис. 6
Пусть теперь $\widehat{BAC}\gt180^\circ$. Покажем, что в этом случае всегда можно провести диагональ из вершины $A$. Для этого продолжим сторону $BA$ многоугольника $M$ за вершину $A$ до первого пересечения со сторонами многоугольника $M$ в некоторой точке $D$. Если $D$ — вершина многоугольника $M$, то $[AD]$ — искомая диагональ. В противном случае точка $D$ лежит на стороне $EF$ многоугольника. Пусть вершина $E$ расположена по разные стороны от прямой $BA$ с вершиной $C$ (рис. 6). Будем двигать переменную точку $P$ на стороне $EF$ от точки $D$ к точке $E$. Тогда переменный отрезок $AP$ заметёт треугольник $ADE$. Если в треугольнике $ADE$ нет вершин многоугольника $M$, то $[AE]$ — искомая диагональ. Если же таковые найдутся, то мы обязательно наткнёмся на одну из них при повороте отрезка $AP$ от положения $[AD]$ до положения $[AE]$. Отрезок от вершины $A$ до ближайшей к $A$ вершине на отрезке $AP$, впервые «встретившем» вершины многоугольника $M$, будет искомой диагональю.
Лемма доказана.
Рис. 7
На рисунках 7, а и 7, б приведены примеры невыпуклых $(2k)$-угольника и $(2k+1)$-угольника, для которых оценка $\left[\dfrac n2\right]$ достигается.
Таким образом, наибольшее число вершин невыпуклого n-угольника, из которых нельзя провести ни одной диагонали, равно $\left[\dfrac n2\right]$.
