ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 97985
Темы:    [ Перестройки ]
[ Выпуклые многоугольники ]
[ Разные задачи на разрезания ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Выпуклый 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 перестройки.

Замечания

баллы: 2 + 2 + 3

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

олимпиада
Название Турнир городов
Турнир
Дата 1988/1989
Номер 10
вариант
Вариант осенний тур, основной вариант, 7-8 класс
Задача
Номер 5
журнал
Название "Квант"
год
Год 1989
выпуск
Номер 6
Задача
Номер М1170

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .