=====ММ198=====
 
**Конкурсная задача ММ198** (8 баллов) 

Будем говорить, что n-угольник относится к классу s, если его можно триангулировать на n-2 треугольника внутренними диагоналями в точности s различными способами. Найти три наименьших и три наибольших значения s для n = 20.

**Решение**

Привожу решения {{:marathon:мм198_fiviol.doc|Виктора Филимоненкова}}, {{:marathon:mm198_полубасов.pdf|Олега Полубасова}} и {{:marathon:kazmerchuk_pr_198.docx|Анатолия Казмерчука}}. 

**Обсуждение**

На ММ198 получено наименьшее в 20-м туре количество решений. По-видимому, это свидетельствует о трудности задачи (первоначальная цена задачи - показатель весьма субъективный). Альтернативное объяснение - задача не вызвала интереса участников - не проходит, ввиду максимально возможной эстетической оценки задачи.  Хотя... процитирую комментарий Дмитрия Пашуткина "Мне показалось, что  эта задача из тех, интерес к которым растет прямо пропорционально времени, затраченному на их решение, из разряда "аппетит приходит во время еды" :) Условие на первый взгляд создает впечатление громоздкости требуемых для решения построений, но стоит только взяться и дальше уже оторваться невозможно."

Отмечу два разных подхода, примененных участниками к конструированию нужных многоугольников: "склеивание" многоугольников с меньшим числом сторон по общей стороне; "вдавливание" некоторых вершин выпуклого многоугольника.
Для получения максимальных значений s конкурсанты естественно использовали второй подход. Для малых значений s большинство конкурсантов использовали первый подход и "уперлись" в случай s=11. В то время как "вдавливание" (см. решение Олега Полубасова) позволяет легко преодолеть этот барьер.

В некоторых решениях (например, у Анатолия Казмерчука) приведены (достаточно легко находимые) полные списки возможных значений s для n < 6. Усилю этот результат, списком для n = 7:\\
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 18, 19, 23, 28, 42}.\\
Разумеется, можно продвинуться и дальше. Но задача описания всех возможных значений s (или хотя бы их количества) для произвольного "n", мягко говоря, очень трудна.
Рост n приводит некому "фрактально-комбинаторному взрыву". "Фрактально" - потому что в формулах для подсчета плодятся самоподобные подформулы. А "взрыву" - потому что плодятся они весьма активно.

Затруднено даже продвижение в изучении максимально возможных значений s. Это затруднение вызвано тем, что с ростом n, значения s, полученные однотипным формулам могут меняться местами (иногда совпадая).
Этот момент описан в решении Анатолия Казмерчука: Действительно, подставляя разные n в формулы C<sub>n-2</sub>-C<sub>n-3</sub>-2C<sub>n-4</sub> и C<sub>n-2</sub>-2C<sub>n-3</sub>+C<sub>n-4</sub> (соответствующие возможным классам n-угольников) получим:\\ 
для n=7 18 и 19 соответственно;\\
для n=8 оба раза по 62;\\
для n=9 213 и 207.  

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

А здесь приведу первый (если я тоже чего-то не пропустил) пропущенный случай в "гарантированном" списке Олега.
У 20-угольника на рисунке 1 отсутствуют внешние диагонали A<sub>17</sub>A<sub>20</sub> и A<sub>18</sub>A<sub>20</sub>. Поэтому он относится к классу C<sub>18</sub>-C<sub>17</sub>-C<sub>16</sub>=312636240
{{ :marathon:20-2.png |рисунок 1}}
Если же немного сместить вправо вершину A<sub>19</sub> (рис. 2), то исчезнут триангуляции, содержащие диагональ A<sub>1</sub>A<sub>18</sub>. Это в точности триангуляции выпуклого 18-угольника A<sub>1</sub>A<sub>2</sub>...A<sub>18</sub>. Поэтому у 20-угольника на рисунке 2 в точности C<sub>18</sub>-C<sub>17</sub>-2C<sub>16</sub>=277278570 триангуляций.
{{ :marathon:20-3.png |рисунок 2}}

**Награды**

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

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