=====ММ220=====

**Конкурсная задача ММ220** (15 баллов)

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

**Решение**

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

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

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

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

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

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

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

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

**Награды**

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

**Эстетическая оценка задачи - 4.7 балла**
----
[[Table_for_A279681|Приложение]]
----