Разбиения выпуклого многоугольника
“Разбиения
выпуклого многоугольника”
Скращук
Дмитрий ( г. Кобрин)
П.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 .Число разбиений, входящих в эту группу совпадает с числом правильных
разбиений (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-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=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)
Каждый n-угольник можно
разбить на (n-2) треугольника, из которых можно сложить (n-3) четырехугольника, причем каждый четырехугольник будет иметь
диагональ. Но в четырехугольнике можно провести 2 диагонали, значит в
(n-3) четырехугольниках
можно провести (n-3)
дополнительные диагонали. Значит, в каждом
правильном разбиении можно провести (n-3) диагонали
удовлетворяющих условию задачи.
П.2.2. Найдем количество во всех
диагоналей правильных всех разбиениях, которые пересекают внутри только две
диагонали.
Проверяя на частных случаях, пришли к
предположению, что количество диагоналей в выпуклых n-угольниках
равно произведению количества разбиений на (n-4), где n ≥ 5
Докажем предположение, что 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 раз.
выбрали
Выделим в данном выпуклом 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))раз, то есть существуют
Окончательно получаем: Pkn=(n- (k+2))Аn , где (*).