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

	Загрузить архив:
	Файл: ref-8800.zip (60kb [zip], Скачиваний: 69) скачать

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

Скращук Дмитрий        ( г. Кобрин)

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

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

P₁, P₂ , … ,P_n–вершины выпуклого n-угольника, А_n- число его правильных разбиений. Рассмотрим диагональ многоугольника P_iP_n.В каждом правильном разбиени P₁P_n принадлежит какому-то треугольнику P₁P_iP_n, где1

Пусть i=2 – одна группа правильных разбиений, которая всегда содержит диагональ P₂P_n.Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (n-1) угольника P₂P₃…Pn, то есть равно А_n-1.

Пусть i=3 – одна группа правильных разбиений, которая всегда содержит диагональ P₃P₁ и P₃P_n.Следовательно, число правильных разбиений, входящих в эту группу, совпадает счислом правильных разбиений (n-2)угольникаP₃P₄…Pn, то есть равно А_n-2.

При i=4 среди треугольниковразбиение непременно содержит треугольник P₁P₄P_n.К нему примыкают четырехугольник P₁P₂P₃P₄и (n-3)угольник P₄P₅ …Pn.Число правильных разбиений четырехугольника равно A_4, число правильных разбиений (n-3) угольника равно

А_n-3.Следовательно, полное число правильных разбиений, содержащихся в этой группе, равно

А_n-3A_4.Группы с i=4,5,6,… содержат А_n-4A_5, А_n-5A_6,… правильных разбиений.

При i=n-2 число правильных разбиений в группе совпадает с числом правильных разбиений в группе с i=2,то есть равно   А_n-1.

Поскольку А₁=А₂=0, А₃=1, A₄=2 и т.к. n³ 3, то число правильных разбиений равно:

А_n=А_n-1+А_n-2+А_n-3 A₄+А_n-4 A₅+ … + A ₅А_n-4+ A₄А_n-3+ А_n-2+ А_n-1.

Например:

A ₅= A₄+ А₃+ A₄=5

A₆= A₅+ А₄+ А₄+ A₅=14

A₇= A₆+ А₅+ А_{4 *}А₄+А₅+ A₆ =42

A₈= A₇+ А₆+А_5*А₄+ А_4*А₅+А₆+ A₇ =132

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

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

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

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

(n-3) четырехугольниках можно провести (n-3)

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

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

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

     Докажем предположение, что P²_n=(n-4)А_{n ,} где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:

-угольник (где dÎN),

Будем выделять из выпуклого n-угольника

n-угольника, причем выделением считается получение последующего a-угольника из предыдущего,

используя не менее двух диагоналей. Выделение ведется до тех пор, пока не получится четырехугольник или треугольник (r = 4 или r = 3 (r – остаточный коэффициент)). Назовемкаждое такое выделение циклом и введем величину, которая будет “считать” их (d). Для каждого d существует 2^d+1 многоугольников, первый многоугольник для данного d ,будет (2^d+1+1)-угольником. Для первой половины (для данного d) многоугольников r = 3, для второй - r = 4. Последним многоугольником, для которого r = 3 будет (3×2^d)-угольником. Окончательно получаем: r = 3, если nÎ[2^d+1+1; 3×2^d], в противном случае 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[2²+1; 2³]

                                d=2, n[2³+1; 2⁴]              

                                d=3, n[2⁴+1; 2⁵]

                                             …

Зависимость d от n-логарифмическая по основанию 2; становится очевидным равенство: d=[log₂(n-1)]-1. Выразим k через n:

k=2([log₂ (n-1)]-1),если nÎ[2^[log2(n-1)]+1; 3×2^{[log2(n-1)]-1}]

                   или

k=2([log₂(n-1)]-1)+1= 2[log₂ (n-1)]-1, если nÏ[2^[log2(n-1)]+1; 3×2^{[log2(n-1)]-1}]

Так как  k – максимум пересечений, то уместны неравенства:

k≤2([log₂ (n-1)]-1),если nÎ[2^[log2(n-1)]+1; 3×2^{[log2(n-1)]-1}]

                       или                                                                     (*)

k≤2[log₂ (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, a_m=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 главных диагоналей.

Окончательно получаем: P^k_n=(n- (k+2))А_{n ,} где (*).