===========ММ198=============== ММ198 (8 баллов)
Будем говорить, что n-угольник относится к классу

, если его можно триангулировать на

треугольника внутренними диагоналями в точности

различными способами. Найти три наименьших и три наибольших значения

для

.
РешениеПривожу решения Виктора Филимоненкова, Олега Полубасова и Анатолия Казмерчука.
Вложение:
198_fiviol.doc [62 Кб]
Скачиваний: 726
Вложение:
MM198_Полубасов.pdf [417.94 Кб]
Скачиваний: 689
Вложение:
Kazmerchuk_pr_198.docx [24.38 Кб]
Скачиваний: 669
ОбсуждениеНа ММ198 получено наименьшее в 20-м туре количество решений. По-видимому, это свидетельствует о трудности задачи (первоначальная цена задачи - показатель весьма субъективный). Альтернативное объяснение - задача не вызвала интереса участников - не проходит, ввиду максимально возможной эстетической оценки задачи. Хотя... процитирую комментарий Дмитрия Пашуткина "Мне показалось, что эта задача из тех, интерес к которым растет прямо пропорционально времени, затраченному на их решение, из разряда "аппетит приходит во время еды" :) Условие на первый взгляд создает впечатление громоздкости требуемых для решения построений, но стоит только взяться и дальше уже оторваться невозможно."
Отмечу два разных подхода, примененных участниками к конструированию нужных многоугольников: "склеивание" многоугольников с меньшим числом сторон по общей стороне; "вдавливание" некоторых вершин выпуклого многоугольника.
Для получения максимальных значений

конкурсанты естественно использовали второй подход. Для малых значений

большинство конкурсантов использовали первый подход и "уперлись" в случай

. В то время как "вдавливание" (см. решение Олега Полубасова) позволяет легко преодолеть этот барьер.
В некоторых решениях (например, у Анатолия Казмерчука) приведены (достаточно легко находимые) полные списки возможных значений

для

. Усилю этот результат, списком для

:

.
Разумеется, можно продвинуться и дальше. Но задача описания всех возможных значений

(или хотя бы их количества) для произвольного "n", мягко говоря, очень трудна.
Рост

приводит некому "фрактально-комбинаторному взрыву". "Фрактально" - потому что в формулах для подсчета плодятся самоподобные подформулы. А "взрыву" - потому что плодятся они весьма активно.
Затруднено даже продвижение в изучении максимально возможных значений

. Это затруднение вызвано тем, что с ростом

, значения

, полученные однотипным формулам могут меняться местами (иногда совпадая).
Этот момент описан в решении Анатолия Казмерчука: Действительно, подставляя разные

в формулы

и

(соответствующие возможным классам n-угольников) получим:
для

18 и 19 соответственно;
для

оба раза по 62;
для

213 и 207.
Очередной раз я испытывал определенные затруднения при распределении призовых баллов. Предвосхищая чаяния ведущего, многие участники не ограничились шестью требуемыми значениями

. Понятно, что их усилия должны быть поощрены дополнительными баллами. В значительно меньшей степени понятно что лучше: продвинуться в нахождении больших значений дальше конкурентов, но при этом пропустить некоторые значения в "гарантированном" списке, или ограничиться меньшим количеством значений

, не доходя до пропущенного значения. Итоги моих сомнений см. в разделе
"Награды".
А здесь приведу первый (если я тоже чего-то не пропустил) пропущенный случай в "гарантированном" списке Олега.
У 20-угольника на рисунке 1 отсутствуют внешние диагонали

и

. Поэтому он относится к классу


Если же немного сместить вправо вершину

(рис. 2), то исчезнут триангуляции, содержащие диагональ

. Это в точности триангуляции выпуклого 18-угольника

. Поэтому у 20-угольника на рисунке 2 в точности

триангуляций.
НаградыЗа решение задачи ММ198 участникам начислены следующие призовые баллы:
Олег Полубасов и Анатолий Казмерчук - по 11;
Сергей Половинкин - 10;
Виктор Филимоненков и Дмитрий Пашуткин - по 8;
Ариадна - 6.
Эстетическая оценка задачи - 5 баллов