Информация о задаче

Задача 58118

Тема:

[

Выпуклые многоугольники

]

Сложность: 7
Классы: 8,9

Прислать комментарий

Условие

Выпуклый n-угольник разрезан на треугольники непересекающимися диагоналями. Рассмотрим преобразование такого разбиения, при котором треугольники ABC и ACD заменяются на треугольники ABD и BCD. Пусть P(n) — наименьшее число преобразований, за которое любое разбиение можно перевести в любое другое. Докажите, что: а) P(n) $\ge$ n - 3; б) P(n) $\le$ 2n - 7; в) P(n) $\le$ 2n - 10 при n $\ge$ 13.

Решение

а) Пусть A и B — соседние вершины n-угольника. Рассмотрим разбиение n-угольника диагоналями, выходящими из вершины A, и разбиение диагоналями, выходящими из вершины B. У этих разбиений нет общих диагоналей, а каждое преобразование изменяет только одну диагональ.
б) Индукцией по n легко доказать, что любое разбиение можно перевести в разбиение диагоналями, выходящими из данной вершины A, не более чем за n - 3 преобразования. Действительно, при n = 4 это очевидно. При n > 4 всегда можно сделать одно преобразование так, чтобы появилась диагональ, выходящая из вершины A (если такой диагонали не было). Эта диагональ разбивает n-угольник на k-угольник и l-угольник, где k + l = n + 2. Остается заметить, что (k - 3) + (l - 3) + 1 = n - 3.
Ясно также, что если m диагоналей разбиения уже выходят из вершины A, то нужно не более n - 3 - m преобразований, т. е. m преобразований можно сэкономить.
Если заданы два разбиения, то их можно перевести в разбиение диагоналями, выходящими из вершины A, за 2(n - 3) преобразований. Одно преобразование можно сэкономить, выбрав в качестве A вершину, из которой выходит одна из диагоналей одного из разбиений. Поэтому от любого разбиения можно перейти к любому другому не более чем за 2n - 7 преобразований (пройдя через разбиение диагоналями, выходящими из вершины A).
в) Два разбиения содержат 2(n - 3) диагоналей, поэтому в среднем из каждой вершины выходит ${\frac{4(n-3)}{n}}$ = 4 - ${\frac{12}{n}}$ диагоналей двух данных разбиений. При n $\ge$ 13 это число больше 3, поэтому найдется вершины, из которой выходят по крайней мере 4 диагонали данных разбиений. Выбрав ее, можно сэкономить не одно, а четыре преобразования.

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


книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	22
Название	Выпуклые и невыпуклые многоугольники
Тема	Выпуклые и невыпуклые фигуры
параграф
Номер	1
Название	Выпуклые многоугольники
Тема	Выпуклые многоугольники
задача
Номер	22.007.1