Задача 67277

Темы:    [ Оценка + пример ] [ Планарные графы. Формула Эйлера ] [ Теория графов (прочее) ]

Сложность: 5 Классы: 8,9,10,11

Условие

Автор: Закорко П.

У Карабаса-Барабаса есть большой участок земли в форме выпуклого $12$-угольника, в вершинах которого стоят фонари. Карабасу-Барабасу нужно поставить внутри участка некоторое конечное число фонарей, разделить его на треугольные участки с вершинами в фонарях и раздать эти участки актёрам театра. При этом каждый внутренний фонарь должен освещать не менее шести треугольных участков (фонарь светит недалеко, только на те участки, в вершине которых стоит). Какое максимальное количество треугольных участков может раздать Карабас-Барабас актёрам?

Решение

Нетрудно привести пример, в котором таких участков $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$.

Ответ

24.

Замечания

Классическая задача Дидоны состоит в нахождении среди всех фигур с данным периметром фигуру наибольшей площади (ответ в ней очень естественный: круг — но доказать это не так уж просто). «Задача Карабаса-Барабаса» немного напоминает задачу Дидоны: в ней тоже надо максимизировать «площадь» (количество треугольных участков) при фиксированном «периметре».

И если нарисовать по линиям треугольной сетки любой многоугольник периметра 12 и площади S треугольничков, то мы увидим схему разбиения участка Карабаса на S треугольных участков (буквально так, правда, получаются только схемы, в которых каждый внутренний фонарь освещает ровно 6 участков).

Источники и прецеденты использования

олимпиада
Название	Турнир им.Ломоносова
номер/год
Год	2023
задача
Номер	8