|
||||||||||||||||||
|
СодержаниеММ220Конкурсная задача ММ220 (15 баллов) Найти наименьшее v такое, что существует многогранник, имеющий v вершин и 2016 диагоналей, а многогранника, имеющего v+1 вершину и 2016 диагоналей, не существует. Решение
Привожу все поступившие решения этой трудной задачи: Анатолия Казмерчука, Олега Полубасова и Владислава Франка (как обычно сохранившего в итоговом решении весь тернистый путь к нему). Обсуждение До финиша 22-го марафонского конкурса добрались 3 (с лишним )участника. С учетом тенденций прошлых конкурсов и сложности заключительной задачи такой итог был вполне предсказуем, хотя ведущий, с присущим ему оптимизмом, до последнего надеялся на лучшее. Как это часто практикуется в Марафоне, вопрос задачи ММ220 был частным. Но в данном случае обобщение задачи не только естественно, но, по сути, необходимо. Поскольку проще всего искать ответ к задаче, исследуя вопрос о возможных количествах диагоналей многогранников с фиксированным числом вершин в общем виде. В связи с этим обстоятельством прибавки за обобщение и рассмотрение других случаев задачи несущественны по отношению к базовой стоимости.
Возможные количества диагоналей, а также мощности множеств возможных количеств диагоналей для относительно небольших значений v приведены в Приложении. Интересно, что вторая из этих последовательностей обнаружилась в OEIS: A023536. При этом в описании последовательности никакие диагонали многогранников не упоминались. В этом списке не хватает не только тривиальных случаев, типа «Наименьшее возможное количество диагоналей многогранников с данным числом граней (вершин)», но и нескольких содержательных вариаций. Наибольшие возможные количества диагоналей многогранников с данным числом вершин описываются треугольными числами. А вот , например, вопрос о наименьшем возможном количестве диагоналей простых многогранников с данным числом вершин (коих в данном случае, разумеется должно быть четное число) ждет своего исследователя. Любопытно, что исчерпывающее описание возможных значений количеств диагоналей многогранников с данным числом вершин удалось получить вопреки тому обстоятельству, что задача существования многогранников с требуемым вектором граней (участвующим в формуле подсчета числа диагоналей) в общем виде (насколько мне известно) до сих пор не решена. (Отмечу, что условия (2) - (5) из решения Олега Полубасова, насколько я могу судить, не дают решения для общего случая.) Я пробовал применить технику (введение параметра, отвечающего за количество вершин вне грани с наибольшим числом сторон), приведшую к полному описанию возможных значений количеств диагоналей многогранников с данным числом вершин, к аналогичным задачам в случаях, когда фиксируется количество граней или ребер. Но ничего хорошего из этого не вышло. Вместо отрезков натурального ряда, сплошь заполненных возможными значениями, возникает какое-то решето Возможно, иной подход окажется удачнее. Но «ручное» вычисление начальных значений A279647 и A279679 оптимизма не внушает - каких-либо закономерностей не видно. Награды
За решение и обобщение ММ220 Анатолий Казмерчук получает 17 призовых баллов, а Олег Полубасов и Владислав Франк - по 15 призовых баллов. Эстетическая оценка задачи - 4.7 балла
|
|||||||||||||||||
|
||||||||||||||||||
|