Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

     Докажем предположение, что P2n=(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:

Будем выделять из выпуклого 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 раз.

Рекомендуем скачать другие рефераты по теме: отчет по производственной практике, образец титульный реферата.



Предыдущая страница реферата | 1  2  3 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки