В выпуклом $n$-угольнике ($n\gt4$) никакие три диагонали не проходят через одну точку внутри многоугольника. Какое наибольшее число диагоналей в нём можно провести так, чтобы все части, на которые они разобьют $n$-угольник, оказались треугольниками?
Ответ:$\left[\dfrac{3n}2\right]-4$ (где $[x]$ — целая часть $x$). Разбиения, приведённые на рисунке 1, показывают, что максимальное число $f(n)$ диагоналей, удовлетворяющих условию задачи, при $n=2m$ не меньше $3m-4=\left[\dfrac{3n}2\right]-4$, а при $n=2m+1$ не меньше $3m-3=\left[\dfrac{3n}2\right]-4$. Теперь осталось доказать, что $$
f(n)\le\left[\dfrac{3n}2\right]-4.\tag{*}
$$
Для этого нам понадобится следующая:
Лемма.Если некоторый набор диагоналей $n$-угольника $(n\ge5)$ разбивает его на треугольники, то хотя бы одна из этих диагоналей не пересекается с остальными. (Пересечения в вершинах многоугольника мы не учитываем.)
Рис. 2Рис. 3
Для доказательства леммы заметим, что никакая диагональ не может пересекаться более чем с одной другой диагональю: в противном случае один из кусков разбиения, примыкающих к участку диагонали между соседними точками пересечения, не был бы треугольником, так как сумма его углов оказалась бы больше $180^\circ$ (рис. 2). Допустим теперь, что любая диагональ пересекается с какой-то из остальных, причём только с одной. Пусть $AC$ и $BD$ — такие пересекающиеся диагонали (рис. 3). Поскольку $n\ge5$, хотя бы одна из сторон четырёхугольника $ABCD$, например $AB$, является диагональю (а не стороной) данного $n$-угольника. Диагональ $AB$ входит в наш набор, так как в противном случае кусок многоугольника, примыкающий к ломаной $AOB$, где $O$ — точка пересечения $AC$ и $BD$, не будет треугольником. Следовательно, существует диагональ, пересекающая $AB$. Но эта диагональ обязана пересечь также $AC$ или $BD$, что противоречит сделанному выше замечанию.
Рис. 4
Пользуясь леммой, неравенство (*) можно доказать индукцией по $n$ (при $n=3$ и $n=4$ оно очевидно). Пусть оно доказано для всех $k$, $3\le k\lt n$, где $n\ge5$. Рассмотрим $n$-угольник, разбитый диагоналями на треугольники. По лемме, одна из диагоналей не пересекается с остальными. Предположим, что она делит $n$-угольник на $p$-угольник и $q$-угольник (рис. 4). Тогда $3\le p$, $q\lt n$ и $p+q=n+2$, и число проведённых диагоналей по предположению индукции не превосходит
$$
\begin{gather*}
1+f(p)+f(q)\le\left[\dfrac{3p}2\right]+\left[\dfrac{3q}2\right]-7\le\\
\le\left[\dfrac{3(p+q)}2\right]-7=\left[\dfrac{3n}2+3\right]-7=\left[\dfrac{3n}2\right]-4,
\end{gather*}
$$
что и требовалось доказать.
