Олимпиадная задача: минимальное число перестроек в разбиении выпуклого n-угольника
Задача
Выпуклый n-угольник разрезан непересекающимися диагоналями на треугольники. Разрешается проделывать следующее преобразование (перестройку): взяв пару треугольников ABD и BCD с общей стороной, заменить их на треугольники ABC и ACD. Пусть P(n) – наименьшее число перестроек, за которое можно перевести каждое разбиение в любое. Докажите, что
а) P(n) ≥ n – 3;
б) P(n) ≤ 2n – 7;
в) P(n) ≤ 2n – 10 при n ≥ 13.
Решение
a) Рассмотрим соседние вершины A и B. Обозначим через P1 разбиение, в котором все n – 3 диагонали выходят из вершины A, а через P2 – разбиение, в котором все диагонали выходят из B. Заметим, что в P2 ни одна диагональ не выходит из A. Поскольку за одну перестройку добавляется не более одной диагонали, выходящей из A, то для преобразования P2 в P1 требуется не менее n – 3 перестроек. б) Предположим, что мы хотим преобразовать P3 в P4, где P3 и P4 – два произвольных разбиения. Пусть A – вершина, из которой выходит хотя бы одна диагональ P4, а P1 – перестройка, определенная в а). Покажем, что можно преобразовать P3 в P1, добавляя при каждой перестройке по одной диагонали, выходящей из A. Пусть диагональ AC ещё не проведена. Тогда её начало принадлежит одному из треугольников ADE разбиения, причем DE – диагональ. Поэтому к ней с другой стороны прилегает некий треугольник DEF разбиения (F может совпадать с B). Проведя перестойку четырёхугольника ADFE, мы добавим диагональ AF. Итак, для указанного преобразования нужно не более n – 3 перестроек. Для преобразования P1 в P4 необходимо столько же перестроек, сколько для обратного преобразования P4 в P1, то есть не более n – 4, поскольку одна диагональ уже стоит на своём месте. в) Всего в P3 и P4 имеется 2n – 6 > 3n/2 диагоналей. Значит, найдётся вершина, из которой выходит не менее четырёх диагоналей. Обозначим её через A и повторим рассуждения пункта б), сэкономив при этом 4 перестройки.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь