Обсуждение и разбор марафонских задач

[VAL]

===========ММ198===============

ММ198 (8 баллов)

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

Решение

Привожу решения Виктора Филимоненкова, Олега Полубасова и Анатолия Казмерчука.

Вложение:

198_fiviol.doc [62 Кб]
Скачиваний: 630

Вложение:

MM198_Полубасов.pdf [417.94 Кб]
Скачиваний: 593

Вложение:

Kazmerchuk_pr_198.docx [24.38 Кб]
Скачиваний: 576

Обсуждение

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

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

В некоторых решениях (например, у Анатолия Казмерчука) приведены (достаточно легко находимые) полные списки возможных значений $s$ для $n\le 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_{n-2}-C_{n-3}-2C_{n-4}$ и $C_{n-2}-2C_{n-3}+C_{n-4}$ (соответствующие возможным классам n-угольников) получим:
для $n=7$ 18 и 19 соответственно;
для $n=8$ оба раза по 62;
для $n=9$ 213 и 207.

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

А здесь приведу первый (если я тоже чего-то не пропустил) пропущенный случай в "гарантированном" списке Олега.
У 20-угольника на рисунке 1 отсутствуют внешние диагонали $A_{17}A_{20}$ и $A_{18}A_{20}$. Поэтому он относится к классу $C_{18}-C_{17}-C_{16}=312636240$

Если же немного сместить вправо вершину $A_{19}$ (рис. 2), то исчезнут триангуляции, содержащие диагональ $A_1A_{18}$. Это в точности триангуляции выпуклого 18-угольника $A_1A_2\dots A_{18}$. Поэтому у 20-угольника на рисунке 2 в точности $C_{18}-C_{17}-2C_{16}=277278570$ триангуляций.


Награды

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

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

[VAL]

Текущее положение участников в XX туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 191 & 192 & 193 & 194 & 195 & 196 & 197 & 198 & \Sigma \\ \hline & \textit{Номинал задачи} & \textit{4} & \textit{5} & \textit{6} & \textit{6} & \textit{7} & \textit{9} & \textit{5} & \textit{8} & \textit{50} \\ \hline 1.& Олег Полубасов & 5 & 5 & 6 & 6 & 10 & 9 & 6 & 11 & 58 \\ \hline 2.& Сергей Половинкин & 5 & 4 & 5 & 6 & 7 & 9 & 5 & 10 & 51 \\ \hline 3.& Виктор Филимоненков & 4 & 5 & 6 & 6 & 7 & 9 & 5 & 8 & 50 \\ \hline 3.& Анатолий Казмерчук & 4 & 5 & 6 & 6 & 7 & 9 & 2 & 11 & 50 \\ \hline 5.& Дмитрий Пашуткин & 4 & 4 & 6 & 6 & 7 & 9 & 5 & 8 & 49 \\ \hline 6.& Ариадна & 4 & 5 & 6 & 6 & 7 & 9 & 4 & 6 & 47 \\ \hline 7.& Антон Никонов & 4 & 5 & 5 & 6 & 9 & 10 & 1 & - & 40 \\ \hline 8.& Константин Хадаев & 4 & 2 & 4 & 6 & 7 & - & 5 & - & 28 \\ \hline 9.& Владимир Дорофеев & 4 & - & 6 & - & - & - & 5 & - & 15 \\ \hline 10.& Константин Кноп & - & - & - & - & - & 10 & - & - & 10 \\ \hline 11.& Николай Дерюгин & 4 & - & - & - & - & - & - & - & 4 \\ \hline 12.& Денис Артюшин & 3 & - & - & - & - & - & - & - & 3 \\ \hline \end{tabular}

[VAL]

===========ММ199===============

В задаче ММ199 рассматриваются многоугольники, которые могут иметь многоугольные "дыры". Будем говорить, что данный многоугольник имеет род m, если у него m многоугольных дыр. (В частности, в ММ197 и ММ198 рассматриваются многоугольники рода 0.)

ММ199 (5 баллов)

Сколькими внутренними диагоналями и на сколько треугольников триангулируется n-угольник рода m?

Решение

Привожу решения Сергея Половинкина, Ариадны и Анатолия Казмерчука.

Вложение:

Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_199.docx [15.01 Кб]
Скачиваний: 561

Вложение:

Комментарий к файлу: Решение Сергея Половинкина
mm199_polovinkin.pdf [50.21 Кб]
Скачиваний: 645

Вложение:

Комментарий к файлу: Решение Ариадны
199_Ариадна.pdf [498.16 Кб]
Скачиваний: 563

Обсуждение

Задача ММ199 не вызвала затруднений у конкурсантов. При этом методы решения были довольно разнообразны (см. приведенные решения).

Владимир Дорофеев указал, как считать стороны и вершины, в случае "двуугольных" и "одноугольных" дыр, чтобы ответы $n+3m-3$ и $n+2m-2$ оставались верными.

В то же время, Сергей Половинкин указал частные случаи многоугольников с "нормальными" дырами, в которых ответы $n+3m-3$ и $n+2m-2$ перестают быть верными (точнее, единственно верными). Хотя, разумеется, они останутся незыблемы и в этих случаях, если аккуратнее определить триангуляцию многоугольника диагоналями.


Награды

За решение задачи ММ199 Сергей Половинкин и Владимир Дорофеев получают по 6 призовых баллов, а Константин Хадаев, Виктор Филимоненков, Олег Полубасов, Дмитрий Пашуткин, Ариадна и Анатолий Казмерчук - по 5 призовых баллов.

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

[VAL]

Текущее положение участников в XX туре Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 191 & 192 & 193 & 194 & 195 & 196 & 197 & 198 & 199 & \Sigma \\ \hline & \textit{Номинал задачи} & \textit{4} & \textit{5} & \textit{6} & \textit{6} & \textit{7} & \textit{9} & \textit{5} & \textit{8} & \textit{5} & \textit{55} \\ \hline 1.& Олег Полубасов & 5 & 5 & 6 & 6 & 10 & 9 & 6 & 11 & 5 & 63 \\ \hline 2.& Сергей Половинкин & 5 & 4 & 5 & 6 & 7 & 9 & 5 & 10 & 6 & 57 \\ \hline 3.& Виктор Филимоненков & 4 & 5 & 6 & 6 & 7 & 9 & 5 & 8 & 5 & 55 \\ \hline 3.& Анатолий Казмерчук & 4 & 5 & 6 & 6 & 7 & 9 & 2 & 11 & 5 & 55 \\ \hline 5.& Дмитрий Пашуткин & 4 & 4 & 6 & 6 & 7 & 9 & 5 & 8 & 5 & 54 \\ \hline 6.& Ариадна & 4 & 5 & 6 & 6 & 7 & 9 & 4 & 6 & 5 & 52 \\ \hline 7.& Антон Никонов & 4 & 5 & 5 & 6 & 9 & 10 & 1 & - & - & 40 \\ \hline 8.& Константин Хадаев & 4 & 2 & 4 & 6 & 7 & - & 5 & - & 5 & 33 \\ \hline 9.& Владимир Дорофеев & 4 & - & 6 & - & - & - & 5 & - & 6 & 21 \\ \hline 10.& Константин Кноп & - & - & - & - & - & 10 & - & - & - & 10 \\ \hline 11.& Николай Дерюгин & 4 & - & - & - & - & - & - & - & - & 4 \\ \hline 12.& Денис Артюшин & 3 & - & - & - & - & - & - & - & - & 3 \\ \hline \end{tabular}

[VAL]

Тех, кто прислал мне красивые картинки к ММ200, прошу снабдить их обоснованиями: уравнениями прямых, координатами точек, описанием метода построения... В общем, хоть чем-то, дающим возможность верификации ответа.
Разумеется, речь о тех решениях, в которых подобных обоснований нет.

А за то время, пока я буду ждать и проверять, те участники, которые не добрались до ММ200 имеют возможность прислать свои... красивые картинки

[kknop]

Мне кажется, было бы правильно задать некий формат данных (для удобства последующей проверки)
- сначала перечисление точек, потом перечисление, какие отрезки проведены.
Возможно (вариативно) указание, какие точки лежат на каких из отрезков.

Я не предлагаю доводить ситуацию до возможности программной проверки, хотя это было бы совсем круто, - но по крайней мере стоит сделать так, чтобы проверяющему не приходилось додумывать куски решений

[VAL]

kknop в сообщении #937733 писал(а):

Мне кажется, было бы правильно задать некий формат данных (для удобства последующей проверки)
- сначала перечисление точек, потом перечисление, какие отрезки проведены.
Возможно (вариативно) указание, какие точки лежат на каких из отрезков.

Я не предлагаю доводить ситуацию до возможности программной проверки, хотя это было бы совсем круто, - но по крайней мере стоит сделать так, чтобы проверяющему не приходилось додумывать куски решений

Пока суть, да дело, я уже где-то додумал, а где-то программно проверил. Осталось одно решение. Так что, надеюсь, скоро опубликую разбор.

[VAL]

===========ММ200===============

ММ200 (8 баллов)

Обозначим через $T(m)$ максимально возможное количество треугольников, на которые можно разрезать треугольник m прямыми. (Никаких других фигур, при разрезании возникать не должно.)
При каком наименьшем m значение отношения $\frac{T(m)}m$ достигает 4?

Примечание: 8 баллов - это условная цена задачи. Такие баллы будут начисляться за результат (и его обоснование) не хуже, чем у ведущего.

Решение

Привожу решения Виктора Филимоненкова, Сергея Половинкина, Олега Полубасова и Анатолия Казмерчука.

Вложение:

Комментарий к файлу: Решение Олега Полубасова
MM200_Полубасов.pdf [489.41 Кб]
Скачиваний: 569

Вложение:

Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_mm200.doc [214.5 Кб]
Скачиваний: 577

Вложение:

Комментарий к файлу: Решение Сергея Половинкина
mm200_Polovinkin.pdf [104.43 Кб]
Скачиваний: 547

(Решение Виктора Филимоненкова)

Возьмем равносторонний треугольник с длиной стороны 6. Проведем к каждой стороне по 2 параллельных секущих, длиной 5 и 3, и по 3 перпендикулярных секущих, одна из которых высота, а две других составляют $\frac56$ от высоты. Проведенные 15 секущих разбивают треугольник на 60 треугольников, что доказывает неравенство $\frac{T(15)}{15}\ge 4$.
Минимальность пятнадцати секущих могу обосновать только риторическим вопросом: куда ж меньше?!

Для полноты картины, а также в ознаменование завершения юбилейного тура приведу триангуляции Ариадны:

(Триангуляция Ариадны)

...и мою:

(Триангуляция ведущего)

Обсуждение

Трудная дистанция утомила марафонцев. На ММ200 было прислано наименьшее в 20-м туре число ответов. Тем удивительнее, что именно побила рекорд Марафона по разнообразию: пять присланных и один авторский ответ оказались попарно различны! (Точнее, наименьшие искомые $n$ у меня и Олега совпали, но при разных триангуляциях и разных $T(n)$).
Наименьшие найденные участниками значения $n$, начиная с которых $\frac{T(n)}n$ достигает 4, оказались равными 20, 18, 15, 14 и, наконец, 12.

Трудность задачи в том, что ряд T(n) не получается путем добавления на каждом шаге новой прямой к предыдущей конфигурации, а строится значительно сложнее.
Ясно, конфигурация тем лучше, чем больше точек пересечения образуют рассекающие прямые внутри (в крайнем случае на границе) треугольника. Для этого надо избегать параллельности рассекающих прямых, их пресечения вне треугольника, пересечения многих прямых в одной точке. (Менее понятно лишь, как совместить это с сохранением треугольности всех фигур разбиения.)
С этих позиций преимущества решения Анатолия видны сразу. Только ему удалось избежать параллельности рассекающих прямых, и только у него ни в одной точке не пересекаются более трех рассекающих прямых.

Удивление, граничащее с шоком, вызвал у меня тот факт, что я (а судя по присланным решениям, не только я) не смог найти в сети задач, в которых возникает последовательность T(n).
Естественность постановки задачи вступает в явное противоречие с ее нераскрученностью.

Награды

При распределении призовых баллов учтено, что только у Анатолия Казмерчука присутствует обоснование оптимальности решения. (Впрочем, было бы странно, если бы в других решениях была обоснована их оптимальность.)
За решение задачи ММ200 участники получают следующие призовые баллы:
Анатолий Казмерчук - 14;
Олег Полубасов - 10;
Виктор Филимоненков - 7;
Сергей Половинкин - 6;
Ариадна - 5.

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

PS: С некоторыми моментами из решения Анатолия Казмерчука (например, с неравенством, возникшем в пункте 2) я разобрался не до конца. Но не хотел еще дальше откладывать и без того задержавшуюся публикацию решения. Надеюсь, выяснение деталей не приведет к "переоценке ценностей". А если приведет, что ж? Переоценим.

[zmerch]

Добрый день всем

[kknop]

Корень уравнения, которое возникает у Анатолия, равен

$$1/6\cdot \left(4-\frac{2}{(3 \sqrt{33}-17)^{1/3}}+(3 \sqrt{33}-17)^{1/3}\right)$$

.
Я нарисовал его чертеж в Geogebra с этим корнем, там всё точно и действительно пересекается как надо.

А каковы все-таки значения $T(n)$?

[Masik]

Красота! Поздравляю Анатолия с изящным решением! 12 никак не ожидал.
И какая же получилась последовательность T(m)? Нет ли её в OEIS?

[kknop]

Моя картинка к решению А.К.

[Deggial]

Сообщения zmerch отделены в Карантин как неоформленные $\TeX$ом

zmerch в сообщении #938061 писал(а):

Добрый день всем

zmerch, устное замечание за бессодержательное сообщение.

Сообщения kknop отделены в Карантин как неоформленные $\TeX$ом
upd: возвращено

[Masik]

kknop в сообщении #938084 писал(а):

Моя картинка к решению А.К.

Можно заметить, что 22\theta \cong 5.02 \cong 5. Если выбрать треугольник с основанием и высотой, равными 22, то картинку нарисовать будет очень легко. Доказывать она ничего не будет, но нарисовать легко.

[zmerch]

<<С некоторыми моментами из решения Анатолия Казмерчука (например, с неравенством, возникшем в пункте 2) я разобрался не до конца.>>


Пусть $(\Gamma+m-1)/(B_1+B_2)\geqslant3$
Так как $\Gamma=2B_2+B_1-2 $, то $B_1+B_2=(\Gamma+B_1)/2+1$. Далее, $\Gamma+m-1\geqslant3(B_1+B_2)=3((\Gamma+B_1)/2+1)$, и затем $m\geqslant\Gamma/2+3B_1/2+4$, что противоречит условию $\Gamma\geqslant4m$

-- 29.11.2014, 23:13 --

Отличный рисунок. Спасибо kknop'у.

Интересно, что полученная оценка $T(m)\leqslant m^2/3+3$ достигается, если во внутренних узлах пересекается по три прямые, а во внешних ровно по две.

Именно это соображение подсказывает как строить оптимальные конфигурации. Например, при поиске наименьшего m, для которого $T(m)/m\geqslant3$ сразу получаем $m\geqslant8$, но при $m=8$ не удаётся удовлетворить полученному условие во внешних вершинах. Так что $m=9$.