Условие
Выпуклый n-угольник разрезан на треугольники непересекающимися
диагоналями. Рассмотрим преобразование такого разбиения, при
котором треугольники ABC и ACD заменяются на треугольники
ABD и BCD. Пусть P(n) — наименьшее число преобразований,
за которое любое разбиение можно перевести в любое другое.
Докажите, что: а)
P(n)
n - 3; б)
P(n)
2n - 7; в)
P(n)2n - 10 при n13.
Решение
а) Пусть 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) диагоналей, поэтому в среднем
из каждой вершины выходит
= 4 - 
диагоналей двух данных разбиений. При n13 это число больше
3, поэтому найдется вершины, из которой выходят по крайней
мере 4 диагонали данных разбиений. Выбрав ее, можно сэкономить
не одно, а четыре преобразования.
Источники и прецеденты использования
