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


Содержание

№102

Баллы, полученные за решение данной задачи учитываются дважды: в основном Марафоне и в тематическом конкурсе.
А сама задача является прямым продолжением задач ММ57 и ММ101.

Конкурсная задача №102 (КГ-2) (9 баллов)

На какое наименьшее число частей может разбиваться диагоналями выпуклый n-угольник при:
a) n = 6;
b) n = 7;
c) n = 8;
d) n = 9?

Примечание:
Цена задачи указана весьма условно.
Я умею строго обосновывать минимальность известных мне разбиений не для всех указанных n. Соответственно и сами известные мне ответы могут оказаться неверными. 9 призовых баллов будет присуждаться за решения аналогичые моему (имеющие тот же ответ и ту же степень строгости его обоснования). За улучшение известных мне ответов, получение более строгих обоснований, получение (хотя бы частично) обоснованных ответов для бОльших n будут начисляться дополнительные призовые баллы.

Решение

Будем называть диагонали, соединяющие вершины выпуклого многоугольника через одну «короткими»), через две - «средними», через три - «длинными». Точку внутри многоугольника будем называть особенностью порядка k, если в ней пересекаются k+2 диагоналей. Ясно, что особые точки могут возникать только при пересечении средних и длинных диагоналей.

Ординарный n-угольник разбивается своими диагоналями на (n-1)(n-2)(n2-3n+12)/2 частей, что при интересующих нас n составляет 25, 50, 91 и 154 соответственно. Каждая особенность порядка k уменьшает количество частей разбиения на k(k+1)/2. Сумму этих чисел по всем особенностям будем называть дефектом многоугольника. Для решения задачи нужно найти максимальный дефект для каждого из данных n.

a) У шестиугольника всего 3 диагонали, не являющихся короткими. Поэтому в шестиугольнике может возникнуть всего одна особенность порядка 1 (она есть, например, в правильном шестиугольнике). Соответственно максимальный возможный дефект шестиугольника - 1 и минимально возможное число частей разбиения - 24.

b) У семиугольника не может быть особенностей, порядок которых больше 1, (вершин не хватает). А то, что число осбенностей первого порядка не может превышать 3, следует из рассуждений, приведенных в решении задачи ММ104. В то же время 3 особых точки возможны. На рисунке 1 приведены два способа получения семиугольника с тремя особыми точками: достроением правильного пятиугольника; удалением вершины правильноо восьмиугольника. Разумеется, существуют и подходящие семугольники никак не связанные с правильными многоугольниками.

:marathon:102-7.jpg

Итак, максимальный дефект семиугольника - 3, наименьшее возможное число частей разбиения - 47.

c) Представляется очевидным, что максимальный возможный дефект восьмиугольника возникает (в частности) у правильного восьмиугольника. Докажем это утверждение. При наличии особенности второго порядка на средней диагонали не может быть больше двух особенностей. Это легко увидеть на рисунке 2.

:marathon:102-8.jpg

На средней диагонали 1-4 уже есть две особенности Y и V. Точки пересечения нашей диагонали с короткими диагоналями не могут быть особенными. Остаются два кандидата на особые точки. Это X и U. Cделать точку X особой можно за счет смещения диагонали 3-8. Но это неизбежно приведет к тому, что точка Y, а заодно и Z перестанут особыми. Аналогично обстоят дела с точкой V. Поэтому на средней диагонали восьмиугольника не может быть больше двух особых точек. Но у правильного восьмиугольника на каждой средней диагонали их ровно по две. Единственная особенность второго порядка может возникать только на пересечении всех длинных диагоналей восьмиугольника. И у правильного восьмиугольника такая особенность есть. Таким образом, правильный восьмиугольник обладает максимальным дефектом среди всех восьмиугольников: он имеет 8 особых точек первого порядка и одну особую точку второго порядка. Поэтому дефект правильного восьмиугольника - 11, а число частей разбиения 80.

d) Именно к этому пункту относилось примечание к условию. Мне удалось найти девятигольник с дефектом 17. Я полагаю, что это максимальный возможный дефект, но доказывать это не умею.
Как и все конкурсанты, бравшиеся за задачу ММ102, я стартовал с правильного восьмиугольника. Поместим вершины правильного восьмиугольника на единичной окружности, в точках с координатами (cos(Π·i/4); sin(Π·i/4), где i ∈ {0,1,…,7}. В качестве девятой вершины возьмем точку с координатами ((-4-√2)/6; (4-√2)/6) (она тоже лежит на единичной окружности). Не сложно убедиться, что жирные синие точки на рисунке 3 являются особыми, а две наиболее крупные из них - особенности второго порядка.

:marathon:102-9.jpg

Поэтому дефект нашего девятиугольника равен 17, а число частей разбиения - 137.

Обсуждение

Представляется правдоподобной гипотеза: при четных n максимальный дефект имеют правильные n-угольники. Другое утверждение «правильные n-угольники с нечетным числом сторон ординарны» относительно недавно перекочевало из разряда правдоподобных предположений в категорию теорем. Набросок доказательства появился еще в 1936 году в статье G.Bol: Beantwoording van prijsvraag no.17, Nieuw Archief voor WisKunde 18 (1936), p.14-66. Но строгое доказательство было опубликовано лишь в 1998 году: см. «The number of intersection points made by the diagonals of a regular polygon», B. Poonen, M. Rubinstein, SIAM J. on Discrete Mathematics, Vol. 11, No. 1 (1998), p. 135-156.
В этой статье выведена формула для количества частей разбиения правильного n-угольника при любом n. Оказывается, за исключением центра, никакая особенность правильного n-угольника не может иметь порядок выше 5, а особенности пятого порядка (отличные от центра) впервые встречается в правильном 30-угольнике. В целом же формула для числа частей разбиения распадается на 2520 случаев (которые авторам не без изящества удалось запихнуть в одну не слишком громоздкую формулу).

Если принять гипотезу о том, что правильный десятиугольник - «наиболее дефективный» среди десятиугольников, можно получить еще одно косвенное подтверждение тому, что построенный нами девятиугольник имеет максимальный возможный дефект. Добавив к нашему девятиугольнику вершину, симметричную девятой вершине относительно центра исходного восьмиугольника (см. рис. 4), получим десятиугольник с дефектом 26, т.е. с таким же дефектом. как у правильного десятиугольника.

:marathon:102-10.jpg

Андрей Халявин нашел для дефекта девятиугольника некоторую оценку сверку. Но она безусловно сильно завышена (28).

Анатолий Казмерчук тоже нашел было девятиугольник с дефектом 17, но при ближайшем рассмотрении этот объект оказался то ли не совсем выпуклым, то ли не совсем девятиугольником (см. рис. 5).

:marathon:102-9-7.jpg

Награды

Андрей Халявин и Анатолий Казмерчук (нашедшие девятиугольники с дефеком 15) получают по 8 призовых баллов. Николай Дерюгин нарисовал девятиугольник разрезаный 137 частей и поразительно похожий на тот, что приведен на рисунке 3 (только красиво раскрашенный), но не снабдил свою картинку обоснованиями (более строгими чем «похоже, что…»). Кроме того, он не обосновал максимальность дефекта правильного восьмиугольника. Николай получает 6 призовых баллов.

Эстетическая оценка задачи - 5 баллов


 

 


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

marathon/problem_102.txt · Последние изменения: 2013/05/28 11:33 (внешнее изменение)
Powered by DokuWiki  ·  УКЦ ВГПУ 2006