Разбиения выпуклого многоугольника

Разбиения выпуклогомногоугольника СкращукДмитрий г. Кобрин П.1. Выпуклый многоугольник с n сторонами можно разбить натреугольники диагоналями, которые пересекаются лишь в его вершинах. Вывести формулу для числа таких разбиений.Определение назовемправильным разбиением выпуклого n-угольникана треугольники диагоналями, пересекающимися только в вершинах n-угольника.ПустьP1, P2 , ,Pn вершинывыпуклого n-угольника,

Аn- числоего правильных разбиений. Рассмотрим диагональ многоугольника PiPn.В каждомправильном разбиени P1Pn принадлежиткакому-то треугольнику P1PiPn,где1 lt i lt n. Следовательно, полагая i 2,3, , n-1, мы получаем n-2 группы правильных разбиений,включающие все возможные случаи.Пусть i 2 одна группа правильных разбиений, которая всегда содержит диагональ P2Pn .Числоразбиений, входящих в эту группу совпадает с числом правильных разбиений n-1 угольника

P2P3 Pn, то есть равно Аn-1.Пусть i 3 одна группа правильных разбиений, которая всегда содержит диагональ P3P1 и P3Pn.Следовательно, число правильныхразбиений, входящих в эту группу, совпадает с числом правильных разбиений n-2 угольника P3P4 Pn, то есть равно Аn-2.При i 4среди треугольников разбиение непременносодержит треугольник P1P4Pn.Кнему примыкают четырехугольник P1P2P3P4 и n-3 угольник P4P5 Pn.Число правильныхразбиений четырехугольника равно

A4, число правильных разбиений n-3 угольника равноАn-3.Следовательно, полное число правильныхразбиений, содержащихся в этой группе, равноАn-3A4.Группы с i 4,5,6, содержат Аn-4A5, Аn-5A6, правильных разбиений.При i n-2 число правильныхразбиений в группе совпадает с числом правильных разбиений в группе с i 2,то есть равно Аn-1.Поскольку А1 А2 0, А3 1, A4 2 и т.к. n sup3 3, то число правильныхразбиений равно

Аn Аn-1 Аn-2 Аn-3 A4 Аn-4 A5 A 5Аn-4 A4Аn-3 Аn-2 Аn-1. Например A 5 A4 А3 A4 5A6 A5 А4 А4 A5 14A7 A6 А5 А4 А4 А5 A6 42A8 A7 А6 А5 А4 А4 А5 А6 A7 132 П.1. Найдем количество во всех диагоналейправильных разбиениях, которые пересекают внутри только одну диагональ. Проверяя на частных случаях, пришли к предположению, что количестводиагоналей в выпуклых n-угольникахравно произведению количества разбиений на n-3

Докажем предположение, что P1n Аn n-3 Каждыйn-угольник можноразбить на n-2 треугольника, из которых можно сложить n-3 четырехугольника, причем каждый четырехугольник будет иметьдиагональ. Но в четырехугольнике можно провести 2 диагонали, значит в n-3 четырехугольниках можно провести n-3 дополнительные диагонали. Значит, в каждом правильномразбиении можно провести n-3 диагонали удовлетворяющих условию задачи. П.2. Найдем количество во всех диагоналей правильных всех разбиениях,которые пересекают

внутри только две диагонали. Проверяя начастных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равнопроизведению количества разбиений на n-4 , где n 5 Докажемпредположение, что P2n n-4 Аn , где n 8805 5. n-угольник можно разбить на n-2 треугольников из которых можно сложить n-4 пятиугольника, в котором будутсодержаться две непересекающиеся диагонали. Значит, найдется третья диагональ,которая пересекает две другие.

Так как имеется n-4 пятиугольника, значит, существует n-4 дополнительные диагонали удовлетворяющих условию задачи. П.3. Определение 1 Главными диагоналями выпуклого n-угольника называются диагонали, которые разбивают его натреугольники, пересекаясь при этом только в вершинах n-угольника. Замечание их существует n-3 .Определение 2 Дополнительными диагоналями выпуклого n-угольника называютсядиагонали,

которые в данном разбиении пересекают главные диагонали.Замечание их существует менее n-3 .I.Определение k Будем выделять из выпуклого n-угольникаследующимобразом соединяем диагоналями через одну вершину данного n-угольника, причем выделением считаетсяполучение последующего a-угольникаиз предыдущего,используя не менее двух диагоналей. Выделение ведется до техпор, пока не получится четырехугольник или треугольник

r 4 или r 3 r остаточный коэффициент .Назовем каждое такое выделение циклом ивведем величину, которая будет считать их d . Для каждого dсуществует 2d 1 многоугольников,первый многоугольник для данного d ,будет 2d 1 1 -угольником.Для первой половины для данного d многоугольников r 3, для второй - r 4. Последним многоугольником, для которого r 3 будет 3 2d -угольником.Окончательно получаем r 3, если n 2d 1 1 3 2d , в противном случае r 4.

За каждый цикл, еслипроводить дополнительные диагонали, будет добавляться по 2 пересечения и через d циклов число пересеченийдостигнет максимума в полученном данным способом разбиении. Обозначим это числобуквой k.Итак, за 1 цикл 2 пересечения, за 2 цикла 4, за 3 6,очевидна арифметическая прогрессия сразностью 2, a1 2 иколичество членов равным d значит k 2 2 d-1 2d только в том случае, если конечнойфигурой окажется треугольник. В противном случае k 2d 1, так как четырехугольник имеет собственную

диагональ. Рассчитаем d т.к. d 1, n 22 1 23 d 2, n 23 1 24 d 3, n 25 Зависимость dот n- логарифмическая по основанию 2 становитсяочевидным равенство d log2 n-1 -1. Выразим k через n k 2 log2 n-1 -1 , если n 2 log2 n-1 1 3 2 log2 n-1 -1 илиk 2 log2 n-1 -1 1 2 log2 n-1 -1, если n 2 log2 n-1 1 3 2 log2 n-1 -1 Так как k максимумпересечений, то уместны неравенства k 8804 2 log2 n-1 -1 , если n 2 log2 n-1 1 3 2 log2 n-1 -1 или k 8804 2 log2 n-1 -1, если n 2 log2 n-1 1 3 2

log2 n-1 -1 II. Найдем числодополнительных диагоналей m , которые пересекают главные не более k раз.выбрали Выделим в данном выпуклом n-угольнике k 3 -угольник k 3 -угольник если это возможно , зн. уже использовано n 3 -2 k 1 всех отбросили существующих треугольников 1 треугольник n-угольника всего их n-2 ,потомдобавили другой отбросим крайний треугольник и треугольник и добавим к получившейся фигуре ещеопять получили один,имеющий общую с ней сторону, k 3 -угольник не использованный треугольник, тогда

останется k 2 не использованных треугольника, и так далее до тех пор, пока не используем все n-2 треугольника. Очевиднаарифметическая прогрессия с разностью 1, am n-2и c количеством членовравным m. Получим n-2 k 1 m-1 lt gt n-2 k m lt gt m n-k-2 m n- k 2 Значит,в n-угольник можновписать k 3 угольник n- k 2 раз, то есть существуюттакие n- k 2 дополнительныедиагонали, которые пересекут kглавных диагоналей.Окончательно получаем

Pkn n- k 2 Аn , где .