Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ57

Конкурсная задача ММ57 (10 баллов)

Назовем многоугольник ординарным, если он выпуклый и никакие 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) = 4C(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 балла


 

 


Страница: [[marathon:problem_57]]

marathon/problem_57.txt · Последние изменения: 2016/03/27 13:40 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006