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

[VAL]

Cрок приема решений ММ220 продлен до 18:00 20.12.2016 msk.

[VAL]

ММ220 (15 баллов)

Найти наименьшее $v$ такое, что существует многогранник, имеющий $v$ вершин и 2016 диагоналей, а многогранника, имеющего $v+1$ вершину и 2016 диагоналей, не существует.

Решение

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

Обсуждение

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

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

Возможные количества диагоналей, а также мощности множеств возможных количеств диагоналей для относительно небольших значений v приведены по уже упоминавшейся ссылке. Интересно, что вторая из этих последовательностей обнаружилась в OEIS: A023536. При этом в описании последовательности никакие диагонали многогранников не упоминались.
В связи с нынешним конкурсом в OEIS появился и целый ряд новых последовательностей:
A279015 - наибольшее возможное количество диагоналей многогранников с данным числом граней;
A279019 - наименьшее возможное количество диагоналей простых многогранников с данным числом граней;
A279022 - наибольшее возможное количество диагоналей многогранников с данным числом ребер;
A279647 - возможные значения количеств диагоналей многогранников с данным числом граней;
A279679 - возможные значения количеств диагоналей многогранников с данным числом ребер;
A279681 - возможные значения количеств диагоналей многогранников с данным числом вершин.

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

Любопытно, что исчерпывающее описание возможных значений количеств диагоналей многогранников с данным числом вершин удалось получить вопреки тому обстоятельству, что задача существования многогранников с требуемым вектором граней (участвующим в формуле подсчета числа диагоналей) в общем виде (насколько мне известно) до сих пор не решена. (Отмечу, что условия (2) - (5) из решения Олега Полубасова, насколько я могу судить, не дают решения для общего случая.)

Я пробовал применить технику (введение параметра, отвечающего за количество вершин вне грани с наибольшим числом сторон), приведшую к полному описанию возможных значений количеств диагоналей многогранников с данным числом вершин, к аналогичным задачам в случаях, когда фиксируется количество граней или ребер. Но ничего хорошего из этого не вышло. Вместо отрезков натурального ряда, сплошь заполненных возможными значениями, возникает какое-то решето
Возможно, иной подход окажется удачнее. Но "ручное" вычисление начальных значений A279647 и A279679 оптимизма не внушает - каких-либо закономерностей не видно.

Награды

За решение и обобщение ММ220 Анатолий Казмерчук получает 17 призовых баллов, а Олег Полубасов и Владислав Франк - по 15 призовых баллов.
За некоторые соображения по решению Владимир Чубанов получает 3 призовых балла.

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

[grizzly]

VAL и соучастники,
Спасибо за конкурс -- если честно, я на старте не ожидал, что получу столько удовольствия в процессе. Думаю, я мог бы участвовать лучше, только с самого начала я хотел лишь ознакомится, а не рваться в бой; а со второй половины уже не всегда позволяли загрузка на работе, обстоятельства и просто лень :)

Самые яркие впечатления на сейчас: доказательство невозможности 74 диагоналей у 11-гранника (сам никак не мог понять, как подступиться) и последняя задача, по которой я продвинулся (одной дорогой с некоторыми участниками) до 129 вершин и имел вполне реализуемый, думаю, план.

Основная сложность, которую я постоянно испытывал -- понять, до какого уровня подробности нужно раскрывать аргументацию. Вплоть до того, что опускались руки :) Не уверен, в чём здесь причина -- то ли некоторые традиции конкурса позволяют другим участникам выбирать наиболее целесообразный уровень детализации, то ли моя проф.удалённость от математики сказывается (формат форума несколько отличается в этом отношении и не особо помогает).

[VAL]

grizzly в сообщении #1178799 писал(а):

VAL и соучастники,
Спасибо за конкурс -- если честно, я на старте не ожидал, что получу столько удовольствия в процессе.

И Вам спасибо на добром слове! Надеюсь, слово подкрепится делом - участием в следующем конкурсе.

Цитата:

Самые яркие впечатления на сейчас: доказательство невозможности 74 диагоналей у 11-гранника (сам никак не мог понять, как подступиться) и последняя задача, по которой я продвинулся (одной дорогой с некоторыми участниками) до 129 вершин и имел вполне реализуемый, думаю, план.

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

Цитата:

Основная сложность, которую я постоянно испытывал -- понять, до какого уровня подробности нужно раскрывать аргументацию. Вплоть до того, что опускались руки :) Не уверен, в чём здесь причина -- то ли некоторые традиции конкурса позволяют другим участникам выбирать наиболее целесообразный уровень детализации

А нету целесообразного уровня. Как говорится "Каждый выбирает по себе" (с)

[VAL]

Итоговое положение участников в XXII конкурса в рамках Математического марафона
\begin{tabular}{|l|l|r|r|r|r|r|r|r|r|r|r|r|} \hline №& Участники& 211 & 212 & 213 & 214 & 215 & 216 & 217 & 218 & 219 & 220 & \Sigma \\ \hline & \textit{Номинал задачи} & \textit{3} & \textit{4} & \textit{4} & \textit{4} & \textit{4} & \textit{10} & \textit{6} & \textit{5} & \textit{8} & \textit{15} & \textit{63} \\ \hline 1.& Олег Полубасов & 8 & 6 & 7 & 6 & 5 & 13 & 7 & 8 & 12 & 15 & 87 \\ \hline 2.& Анатолий Казмерчук & 6 & 7 & 8 & 7 & 7 & 6 & 7 & 8 & 12 & 17 & 85 \\ \hline 3.& Владислав Франк & 3 & 4 & 5 & 4 & 5 & 11 & 6 & 8 & 8 & 15 & 69 \\ \hline 4.& Виктор Филимоненков & 3 & 4 & 4 & 4 & 4 & - & 6 & 4 & 7 & - & 36 \\ \hline 5.& Владимир Чубанов & 4 & 4 & 4 & 4 & 4 & - & - & 6 & 6 & 3 & 35 \\ \hline 6.& Василий Дзюбенко & 6 & 4 & 4 & 4 & 1 & - & 6 & - & - & - & 25 \\ \hline 6.& Дмитрий Пашуткин & 3 & 4 & 4 & 4 & 4 & - & 6 & - & - & - & 25 \\ \hline 8.& Владимир Дорофеев & 3 & 3 & 4 & 4 & - & - & - & 4 & - & - & 18 \\ \hline 9.& Игорь Ханов & 6 & 3 & 4 & 4 & - & - & - & - & - & - & 17 \\ \hline 10.& Антон Никонов & - & - & - & - & - & 9 & - & - & - & - & 9 \\ \hline 11.& Дмитрий Курашкин & - & - & - & - & 3 & - & - & - & - & - & 3 \\ \hline 12.& Сергей Половинкин & 2 & - & - & - & - & - & - & - & - & - & 2 \\ \hline \end{tabular}

Мои поздравления лауреатам!

[fiviol]

Владимир, традиционное спасибо за интересные задачи и за сам ваш конкурс, который уже более 10 лет для меня является одним из любимых тренажеров для поддержания интеллектуальной формы. К сожалению, не все возможности этого прекрасного тренажера получается в последнее время использовать до конца.
Ваше замечание, что до финиша добралось три человека не вполне справедливо. Остальные тоже добрались, но наш финиш случился немного раньше. :) Бывает же фальстарт - тогда это, наверное, фальшфиниш.

[VAL]

Положение лидирующей группы после 22-го конкурса Марафона
\begin{tabular}{|l|r|r|r|r|r|r|r|r|r|r|r|r|r|c|} \hline Участники \ \ Туры$\to$ &1-10&11&12&13&14&15&16&17&18&19&20&21&22&\Sigma\\ \hline 1. А.Казмерчук &122&61&74&61&45&54&53&51&73&79&69&82&85&909\\ \hline 2. О.Полубасов &268&-&-&-&-&-&64&56&83&97&73&79&87&807\\ \hline 3. В.Филимоненков &229&32&32&22&-&48&55&46&71&53&62&23&36&709\\ \hline 4. С.Половинкин &-&-&80&57&64&56&58&41&74&60&63&36&2&591\\ \hline 5. А.Волошин &45&20&72&61&47&52&54&50&76&3&-&-&-&480\\ \hline 5. В.Франк &379&-&6&-&26&-&-&-&-&-&-&-&69&480\\ \hline 7. Н.Дерюгин &21&30&49&21&20&19&43&18&54&21&4&-&-&300\\ \hline 8. Д.Пашуткин &-&-&41&16&48&43&24&3&-&45&54&-&25&293\\ \hline 9. E.Гужавин &-&-&-&4&34&9&9&21&34&17&-&18&-&146\\ \hline 10. А.Халявин &49&17&6&-&-&43&-&-&-&14&-&-&-&129\\ \hline 11. А.Богданов &112&-&-&-&-&-&-&-&-&-&-&-&-&112\\ \hline 12. К.Веденский &-&30&18&-&17&20&-&-&23&-&-&-&-&108\\ \hline 13. А.Извалов &46&-&-&-&-&-&-&-&34&-&-&15&-&95\\ \hline 14. А.Никонов &80&-&-&-&-&-&-&-&-&38&40&2&9&89\\ \hline 15. И.Козначеев &88&-&-&-&-&-&-&-&-&-&-&-&-&88\\ \hline 16. К.Кноп &75&-&-&-&-&-&-&-&-&-&10&-&-&85\\ \hline 17. В. Колыбасова &-&-&-&-&-&-&-&-&-&10&57&17&-&84\\ \hline 18. Б.Бух &81&-&-&-&-&-&-&-&-&-&-&-&-&81\\ \hline 19. М.Алексеев &80&-&-&-&-&-&-&-&-&-&-&-&-&80\\ \hline 20. Э.Туркевич &9&-&54&11&-&-&-&-&-&-&-&-&-&74\\ \hline 21. А.Винокуров &73&-&-&-&-&-&-&-&-&-&-&-&-&73\\ \hline 21. Д.Милосердов &73&-&-&-&-&-&-&-&-&-&-&-&-&73\\ \hline 23. А.Ларин &-&-&-&7&-&31&29&-&-&-&-&-&-&67\\ \hline 24. Е.Машеров &45&-&-&5&-&4&10&-&-&10&-&-&-&64\\ \hline 25. В.Дзюбенко &-&-&-&-&-&-&-&-&-&-&-&34&25&59\\ \hline \end{tabular}

[VAL]

По следам вопроса, поднятого при разборе ММ215.

VAL в сообщении #1159367 писал(а):

Так что "тетраэдризируемые" (в смысле, изложенном в обсуждении ММ215) многогранники весьма редки.

Пусть $S(M)$ - множество возможных количеств тетраэдров, на которые можно разрезать выпуклый многогранник $M$ способом, описанным в обсуждении ММ215. Вот перечень выпуклых многогранников, для которых $S(M)$ конечно:
пирамиды;
треугольные призмы (и изоморфные им многогранники);
треугольные бипирамиды;
четырехугольные бипирамиды специального вида (для любой пары противоположных вершин оставшиеся четыре компланарны).
И, похоже, все.
Перебор простейших многогранников (имеющих не более 12 ребер) показывает для тех из них, которых нет среди вышеперечисленных, $S(M)$ бесконечно. Разрезая (указанным способом) другие многогранники в каждом конкретном случае легко получить какие-либо многогранники, для которых бесконечность $S(M)$ уже проверена. Но, как оформить это рассуждение в строгое доказательство, я пока не придумал.
У кого-нибудь есть идеи?

Любопытно, что среди многогранников с бесконечным $S(M)$ есть те, у которых дополнение $S(M)$ до $\mathbb N$ тоже бесконечно, и те, которые можно разрезать на любое количество тетраэдров, начиная с некоторого.
Есть такие многогранники, которые указанным способом нельзя разрезать на конечное число тетраэдров, я по-прежнему не знаю.

[Masik]

Всем счастливого Нового Года!
Выступлю коротенько, минут на сорок. Сказать хочется очень много.
Оценка этого конкурса: "восторженное, но нецензурное выражение".

[VAL]

Марафонцев и сочувствующих с Новым годом!

Надеюсь, в наступающем у нас будет мало огорчений и много радостей, одной из которых будет Марафон!

С пламенным липецким приветом, Ведущий.

[kotenok gav]

А как поучаствовать в Марафоне?

[VAL]

kotenok gav в сообщении #1204849 писал(а):

А как поучаствовать в Марафоне?

Для начала дождаться, когда будут опубликованы задачи 23-го конкурса в рамках Марафона.

А затем в отведенные сроки высылать решения конкурсных задач ведущему. И не обсуждать их на форуме до опубликования разбора.

Подробнее с правилами можно ознакомиться здесь.

[kotenok gav]

VAL, а где будут публиковатся задачи?

[VAL]

kotenok gav в сообщении #1204879 писал(а):

VAL, а где будут публиковатся задачи?

Возможно, Вы удивитесь, но задачи Математического Марафона будут публиковаться в теме "Математический марафон", ссылка на которую приведена выше.

[kotenok gav]

Хорошо, а когда они начнут публиковатся?