Максимальное число треугольных участков для Карабаса-Барабаса

Нетрудно привести пример, в котором таких участков $24$:Попробуем доказать, что сделать больше $24$ участков не получится. Рассмотрим сначала более общую ситуацию: пусть есть $n$-угольник с фонарями в вершинах, который разбит на треугольные участки, причём из каждой внутренней вершины (если они есть) выходит по крайней мере $6$ отрезков. Покрасим вершины многоугольника в синий, а все внутренние вершины – в красный. Раскрасим также в синий цвет все треугольники, у которых хотя бы одна из вершин оказалась синей (пример такой раскраски – на рисунке ниже).

Утверждение 1. Синих треугольников не больше, чем $2n-6$.

При каждой из внутренних (красных) вершин сумма по крайней мере $6$ углов равна $360^\circ$, значит, в среднем угол с красной вершиной меньше $60^\circ$. Поскольку среднее значение всех углов треугольников равно $180^\circ : 3 = 60^\circ,$ то угол с синей вершиной в среднем больше $60^\circ$. Сумма углов с синими вершинами равна сумме углов $n$-угольника, то есть $180^\circ (n-2)$. Следовательно, углов с синими вершинами не больше, чем $180^\circ (n-2) : 60^\circ = 3 (n-2).$ Каждая сторона многоугольника является стороной двух углов; вычеркнем из этих углов те, которые идут позже по часовой стрелке (на рисунке такие углы отмечены красным).

После этого в каждом синем треугольнике останется невычеркнутым хотя бы один синий угол, но всего синих углов останется не более $3 (n-2) - n = 2n - 6.$ Значит, синих треугольников не более, чем $2n-6$. Утверждение 2. Если внутри $n$-угольника есть хотя бы одна красная вершина, то найдутся по крайней мере $n$ треугольников, у которых не меньше двух вершин – синие.

Рассмотрим треугольники, примыкающие к сторонам $n$-угольника (у них по крайней мере две вершины – концы этой стороны – синие). Если к каждой стороне примыкает отдельный треугольник, то их ровно $n$ (и, возможно, есть другие треугольники, имеющие две синие вершины) – утверждение доказано. В противном случае есть треугольник, содержащий ровно две стороны многоугольника (три стороны он содержать не может: это означало бы, что сам многоугольник – это треугольник, внутри которого нет красных точек). Отрежем этот треугольник; останется $(n-1)$-угольник с синими вершинами, у которого по-прежнему есть внутри хотя бы одна красная вершина, а все треугольники с хотя бы одной синей вершиной покрашены синим.

В $(n-1)$-угольнике, опять же, либо к каждой стороне примыкает отдельный треугольник, либо есть треугольник, две стороны которого являются сторонами многоугольника. В первом случае мы нашли $n-1$ подходящий треугольник, и ещё $1$ треугольник отрезали на предыдущем шаге – значит, в исходном $n$-угольнике было по крайней мере $n$ треугольников с двумя синими вершинами. Во втором случае снова отрежем этот треугольник и продолжим тот же процесс, получая на каждом новом шаге $n-k$-угольник и $k$ отрезанных треугольников. Рано или поздно процесс остановится, поскольку количество сторон уменьшается; в сумме с отрезанными треугольниками получим $n$ треугольников с хотя бы двумя синими вершинами. Таким образом, утверждение 2 доказано. Рассмотрим теперь ту часть многоугольника, которая не покрашена синим (она может состоять из одного или нескольких многоугольников).

Утверждение 3. Суммарное количество сторон непокрашенных частей не превосходит $n-6$.

Заметим, что сторона непокрашенной части – это отрезок с концами в красных вершинах, являющийся также стороной синего треугольника (ровно одного). В синем треугольнике с такой стороной ровно одна вершина – синяя. Всего синих треугольников в силу утверждения 1 не более, чем $2n-6$, и в силу утверждения 2 по крайней мере $n$ из них имеют две (или все три) синие вершины. Значит, сторон непокрашенной части, как и синих треугольников с одной синей вершиной, не более чем $2n-6 - n = n-6$.

Итак, рассмотрим теперь $12$-угольник из задачи. В нём по утверждению 1 не более $12 \cdot 2 - 6 = 18$ синих треугольников. У оставшейся, непокрашенной, части (или частей) суммарно сторон не более чем $12-6=6$. Отбросим синие треугольники и рассмотрим непокрашенную часть отдельно: снова покрасим синим все вершины на её границе (или границах), а также покрасим синим треугольники, у которых теперь есть хотя бы одна синяя вершина. Поскольку $6-6 = 0$, все треугольники будут покрашены. При этом по утверждению 1 синих треугольников не более $2 \cdot 6 - 6 = 6$.

Значит, всего треугольников в разбиении $12$-угольника может быть не более $18+6 = 24$.