Назовем многоугольник регулярным, если он выпуклый и никакие 3 его диагонали не пересекаются в одной точке внутри многоугольника. Пусть n - число сторон регулярного многоугольника.
1) На сколько частей разбивают диагонали регулярный многоугольник?
2) Верно ли, что при фиксированном n среди частей, на которые разбивается
диагоналями регулярный многоугольник всегда одно и тоже число треугольников?
3) При каком минимальном n в разбиении регулярного многоугольника может
получиться восьмиугольник?
4) Существует ли регулярный многоугольник, в разбиении которого получается
больше пятиугольников, чем треугольников?
5) При каких n существуют разбиения регулярного многоугольника, содержащие
только треугольники и четырехугольники?
Решение
Введем некоторые обозначения.
Диагонали, соединяющие вершины многоугольника через одну, будем называть
"короткими", а диагонали соединяющие противоположные вершины при четном n
и наиболее близкие к противополжным при нечетном n - "длинными".
(Таким образом и у четырехугольника, и у пятиугольника все диагонали являются
короткими и длинными одновременно).
1) Первый пункт задачи №57 представляет собой широко известную задачу.
Наиболее изящный способ решения - применить соотношение Эйлера для плоской
укладки связного графа. Наш многоугольник задает такую укладку, если
в качестве вершин графа рассматривать вершины и точки пересечения диагоналей
многоугольника, а в качестве ребер - стороны исходного многоугольника и
отрезки, на которые разбиваются диагонали.
Обозначим через В, Р и Г количества вершин, ребер и граней графа.
По формуле Эйлера В + Г - Р = 1 (внешняя грань, не являющаяся частью разбиения,
нас не интересует).
Поскольку каждая точка пересечения диагоналей находится в биективном
соответствии с каждой (неупорядоченной) четверкой вершин многоугольника,
количество точек пересечения равно C(n,4). Поэтому В = С(n,4) + n.
Каждая диагональ разбивается на отрезки, количество которых на один больше
числа точек пересечения, лежащих на этой диагонали. При этом каждая точка
пересечения принадлежит двум диагоналям, а всего диагоналей - n(n-3)/2.
Поэтому Р = 2*С(n,4) + n(n-3)/2 + n (последнее слагаемое соответствует
сторонам многоугольника).
Таким Образом, Г(n) = Р(n) - В(n) + 1 = C(n,4) + n(n-3)/1 + 1 =
(n - 1)(n - 2)(n2 - 3n + 12)/24.
2) Нет. Пример: В разбиении семиугольника с вершинами A(-5;0), B(5;0), C(7;3), D(7;6), E(4;7), F(-4;8), G(-7;3) участвуют 32 треугольника. Если же вторую координату вершины C заменить на 4, то треугольников станет 35.
3) При n = 9.
Пример подходящего девятиугольника: A(-50;0), B(50;0), C(70;35), D(70;60),
E(42;72), F(3;80), G(-40;80), H(-60;56), I(-70;30).
Остается показать, что восьмиугольник не может возникнуть при меньшем n.
Т.к в формировании одной части разбиения участвует не более двух диагоналей,
выходящих из одной вершины, и при этом каждая диагональ инцидентна двум
вершинам, восьмиугольник не может возникнуть при n < 8.
Допустим, что восьмиугольник возникает при разбиении восьмиугольника.
Ясно что, части разбиения, примыкающие к сторонам исходжного многоугольника,
являются треугольниками.
Назовем диагонали, на пересечении которых образуется восьмиугольник,
формирующими.
Очевидно, что короткие диагонали не могут быть формирующими (легко видеть,
что части разбиения, примыкающие к коротким сторонам, не более чем пятиугольны)
Тогда из каждой вершины должны выходить две соседние диагонали (одна длинная и
одна "средняя"), формирующие восьмиугольник. При этом каждая такая диагональ
должна пересекать все формирующие диагонали, не имеющие с ней общих вершин.
Пусть ABCDEFGH исходный многоугольник. Длинная диагональ AE (как и любая
длинная диагональ) обязана быть формирующей. Не нарушая общности рассуждений,
можно считать, что AF - вторая формирующая диагональ, инцидентная A.
Тогда дигональ EH тоже обязана быть формирующей, поскольку дагональ BE не
пересекает AF. Остальные 5 формирующих диагоналей должны пересекать дигональ
AE. Но это невозможно, поскольку шесть концов этих диагоналей (по два в
точках B, C, D) лежат по одну сторону от AE и лишь четыре конца (два в точке G
и по одному в точках F и H) - по другую.
Таким образом, восмиугольник не может возникать в разбиении восьмиугольника.
4) Нет.
Легко видеть, что сумма количеств углов всех многогугольников разбиения
зависит только от n. Обозначим эту сумму через У(n). К каждой вершине исходного
многоугольника примыкает n-2 угла, а к каждой точке пересечения диагоналей - 4.
Поэтому У(n) = 4*C(n,4) + n(n-2).
У(n) - 4*Г(n) = -(n-2)2.
Каждый m-угольник разбиения с числом сторон, большим 4, привносит в эту
сумму m-4 единицы. И лишь треугольники дают "отрицательный вклад" (по -1 на
каждый треугольник). Но У(n) - 4*Г(n) является отрицательным при любом
допустимом n. Поэтому количество треугольников превышает в разбиении
суммарное количество всех многоугольников с чмслом сторон, превышающем 4, и,
в частности, пятиугольников.
5) При n = 3 и n = 4.
Короткие диагонали высекают внутри исходного многоугольника многоугольник с
таким же количеством сторон. Легко видеть, что все части разбиения, лежащие
вне этого многоугольника, являются треугольниками, а количество таких
треугольников равно n(n-3).
Применим рассуждение, аналогичное приведенному в пункте 4, к n-угольнику,
высекаемому короткими диагоналями:
У1(n) = У(n) - 3n(n-3), Г1(n) = Г(n) - n(n-3),
У1(n) - 4*Г1(n) = n - 4.
Поэтому, начиная с n, равного 5, внутри многоугольника, ограниченного короткими
диагоналями, обязаны присутствовать части разбиения, имеющие более четырех
сторон.
Oбсуждение
Ситуация третьего пункта задачи легко обощается. Если m нечетно, то m-угольник может (но не обязан) возникать в разбиении регулярного n-угольника, начиная с n = m. Если же m четно, то m-угольник может быть частью разбиения, начиная с n = m+1.
Из рассуждения, приведенного в пятом пункте, следует, что начиная с n = 5, в разбиении регулярного многоугольника появляются многоугольники, имеющие больше четырех сторон. Не сложно показать, что среди них всегда будут пятиугольники. При n = 5 пятиугольником разбиения будет сам многоугльник, высекаемый короткими диагоналями. А для бОльших значений n не менее n/2 пятиугольников будут примыкать с внутренней стороны к коротким диагоналям.
Награды
За правильное решение этой задачи Виктор Филимоненков и Влад Франк получают по 10 призовых баллов.
Эстетическая оценка задачи - 3 балла