П.1. Выпуклый многоугольник с
n сторонами можно разбить на треугольники диагоналями, которые пересекаются лишь в его вершинах. Вывести формулу для числа таких разбиений.
Определение:
назовем правильным разбиением выпуклого n-угольника на треугольники диагоналями, пересекающимися только в вершинах n-угольника.
Пусть P1
, P2
, … ,Pn
–вершины выпуклого n-угольника, Аn
- число его правильных разбиений. Рассмотрим диагональ многоугольника Pi
Pn
.В каждом правильном разбиение P1
Pn
принадлежит какому-то треугольнику P1
Pi
Pn
, где1<i<n. Следовательно, полагая i=2,3, … , n-1, мы получаем (n-2) группы правильных разбиений, включающие все возможные случаи.
Пусть i=2 – одна группа правильных разбиений, которая всегда содержит диагональ P2
Pn
.Число разбиений, входящих в эту группу совпадает с числом правильных разбиений (n-1) угольника P2
P3
…Pn, то есть равно Аn-1
.
Пусть i=3 – одна группа правильных разбиений, которая всегда содержит диагональ P3
P1
и P3
Pn
.
Следовательно, число правильных разбиений, входящих в эту группу, совпадает с числом правильных разбиений (n-2)угольника P3
P4
…Pn, то есть равно Аn-2.
При i=4 среди треугольников разбиение непременно содержит треугольник P1
P4
Pn
.К нему примыкают четырехугольник P1
P2
P3
P4
и (n-3)угольник P4
P5
…Pn.Число правильных разбиений четырехугольника равно A4,
число правильных разбиений (n-3) угольника равно
Аn-3.
Следовательно, полное число правильных разбиений, содержащихся в этой группе, равно
Аn-3
A4.
Группы с i=4,5,6,… содержат Аn-4
A5,
Аn-5
A6,
… правильных разбиений.
При 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)
Докажем предположение, что P1
n
=Аn
(n-3)
Каждый n-угольник можно разбить на (n-2) треугольника, из которых можно сложить (n-3) четырехугольника, причем каждый четырехугольник будет иметь диагональ. Но в четырехугольнике можно провести 2 диагонали, значит в (n-3) четырехугольниках можно провести (n-3) дополнительные диагонали. Значит, в каждом правильном разбиении можно провести (n-3) диагонали удовлетворяющих условию задачи.
П.2.2.
Найдем количество во всех диагоналей правильных всех разбиениях, которые пересекают внутри только две диагонали.
Проверяя на частных случаях, пришли к предположению, что количество диагоналей в выпуклых n-угольниках равно произведению количества разбиений на (n-4), где n ≥ 5
Докажем предположение, что P2
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:
Будем выделять из выпуклого n-угольника
следующим образом: соединяем диагоналями через одну вершину данного n-угольника, причем выделением считается получение последующего a-угольника из предыдущего, используя не менее двух диагоналей. Выделение ведется до тех пор, пока не получится четырехугольник или треугольник (r = 4 или r = 3 (r – остаточный коэффициент)). Назовем каждое такое выделение циклом и введем величину, которая будет “считать” их (d). Для каждого в существует 2d+1
многоугольников, первый многоугольник для данного в ,будет (2d+1
+1)-угольником. Для первой половины (для данного d) многоугольников r = 3, для второй - r = 4. Последним многоугольником, для которого r = 3 будет (3×2d
)-угольником. Окончательно получаем: r = 3, если nÎ[2d+1
+1; 3×2d
], в противном случае r = 4. За каждый цикл, если проводить дополнительные диагонали, будет добавляться по 2 пересечения и через в циклов число пересечений достигнет максимума в полученном данным способом разбиении. Обозначим это число буквой 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
]
…
Зависимость в от 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 главных диагоналей.
Окончательно получаем: Pk
n
=(
n- (k+2))А
n ,
где(*).
Список литературы
Скращук Дмитрий (г. Кобрин). Разбиения выпуклого многоугольника
|