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

П.1. Выпуклый многоугольник с n сторонами можно разбить на треугольники диагоналями,которые пересекаются лишь в его вершинах. Вывести формулу для числа таких разбиений.

Определение: назовем правильнымразбиением выпуклого n-угольника на треугольникидиагоналями, пересекающимися только в вершинах n-угольника.

/>

Пусть P1,P2, … ,Pn–вершинывыпуклого n-угольника, Аn-число его правильных разбиений. Рассмотрим диагональ многоугольника PiPn.В каждом правильном разбиение P1Pnпринадлежит какому-то треугольнику P1PiPn, где1<i<n. Следовательно, полагая i=2,3, …, n-1, мы получаем (n-2) группы правильныхразбиений, включающие все возможные случаи.

Пусть i=2 – однагруппа правильных разбиений, которая всегда содержит диагональ P2Pn<sub/>.Число разбиений, входящих в эту группу совпадает счислом правильных разбиений (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 ³ 3,то число правильных разбиений равно:

Аn=Аn-1n-2n-3 A4+Аn-4 A5+ … + A 5Аn-4+ A4Аn-3+ Аn-2+ Аn-1.

Например:

A 5= A4+А3+ A4=5

/>

A6= A5+А4+ А4+ A5=14

A7= A6+ А5+ А4*А4+А5+A6 =42

A8= A7+ А6+А5*А4+А4*А5+А6+ A7=132

П.2.1. Найдем количество во всехдиагоналей правильных разбиениях, которые пересекают внутри только однудиагональ.

Проверяя на частных случаях, пришли кпредположению, что количество диагоналей в выпуклых n-угольникахравно произведению количества разбиений на (n-3)

Докажем предположение, что P1n=Аn(n-3)

/>

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

П.2.2. Найдем количество во всехдиагоналей правильных всех разбиениях, которые пересекают внутри только дведиагонали.

Проверяя на частных случаях, пришли кпредположению, что количество диагоналей в выпуклых n-угольникахравно произведению количества разбиений на (n-4), где n ≥ 5

Докажем предположение, что P2n=(n-4)Аn, где<sub/>n ≥5.

/> 

n-угольник можноразбить на (n-2) треугольников из которых можно сложить(n-4) пятиугольника, в котором будут содержаться двенепересекающиеся диагонали. Значит, найдется третья диагональ, котораяпересекает две другие. Так как имеется (n-4)пятиугольника, значит, существует (n-4) дополнительныедиагонали удовлетворяющих условию задачи.

П.2.3. Разбиение n-угольника,в котором дополнительные диагонали пересекают главные kраз.

Определение 1: Главными диагоналямивыпуклого n-угольника называются диагонали, которыеразбивают его на треугольники, пересекаясь при этом только в вершинах n-угольника.

Замечание: их существует (n-3).

Определение 2: Дополнительнымидиагоналями выпуклого n-угольника называются диагонали,которые в данном разбиении пересекают главные диагонали.

Замечание: их существует менее (n-3).

I.Определение k:

/> <td/> />
Будем выделять из выпуклого 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/> [24+1; 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≤2([log2(n-1)]-1), еслиnÎ[2[log2(n-1)]+1;3×2[log2(n-1)]-1]

или(*)

k≤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)<=>n-2=k+m<=>m=n-k-2óm=n-(k+2)Значит,в n-угольник можно вписать (k+3)угольник(n-(k+2))раз, то естьсуществуют такие (n-(k+2))дополнительные диагонали, которые пересекут k главныхдиагоналей.

Окончательно получаем: Pkn=(n- (k+2))Аn, где<sub/>(*).

Список литературы

Скращук Дмитрий (г. Кобрин). Разбиениявыпуклого многоугольника

еще рефераты
Еще работы по математике