===========ММ218===============ММ218 (5 баллов)
Найти наименьшее возможное количество диагоналей многогранника, имеющего 2017 ребер.
РешениеПривожу решения Владимира Чубанова, Олега Полубасова, Анатолия Казмерчука и Владислава Франка.
(Решение Владимира Чубанова)
ММ218
Найти наименьшее возможное количество диагоналей многогранника, имеющего 2017 ребер.
Ответ: 1004 диагоналей.
______
Пример на 1004 построить легко (см. рисунок). Поставили треугольную призму "домиком" и с одной стороны -- со стороны
-- добавили 1004 точки в плоскости
(на рисунке отмечена только часть этих точек). Получили 1008 точек основания и 2 точки "сверху".
Количество рёбер:
;
Количество (пространственных) диагоналей: 1004 -- все новые точки соединены с т.
. Других диагоналей нет.
Аргументы в пользу того, что меньше быть не может.
При рассмотрении суммарно всех диагоналей (пространственные + диагонали граней) нетрудно заметить, что наиболее выгодная стратегия лежит не в уменьшении числа вершин и не в разделении вершин по разным граням, а в максимальной консолидации вершин в одной грани-плоскости (поскольку
растёт квадратично, при таком количестве точек это перевешивает остальные стратегии).
Поднять только одну вершину над плоскостью недостаточно -- количество рёбер будет чётным.
Поднять 2 вершины над плоскостью можно несколькими принципиально разными способами, которые несложно перебрать руками и убедиться, что представленный вариант принадлежит множеству самых выгодных.
Кроме того, приведу и свое решение задачи.
(Авторское решение)
Я специально не стал заострять внимание на технических деталях, чтобы не скрыть в них основные (довольно простые) идеи.
Пусть многогранник имеет
вершин,
ребер и
граней, а
- количества сторон граней. Очевидно, что количество диагоналей такого многогранника многогранника вычисляется по формуле:
Легко видеть, что при фиксированных
и
сумма
будет тем меньше, чем равномернее распределены значения
. И, соответственно, тем больше, чем больше самое большое из
(в дальнейшем будем считать, что это
.
При четных
может достигать
. Этот случай соответствует пирамидам, у которых
.
В нашем случае наибольшее значение
достигается при
. Соответствующие многогранники (еще две его грани четырехугольны, а остальные треугольны) легко строится. Их изображения можно найти в некоторых из приводимых решений. По формуле (1) (или в лоб) находим, что для такого многогранника
.
Ясно, что с ростом
уменьшаемое в (1) будет расти, а вычитаемое уменьшаться. Следовательно будет расти и
.
Картина, возникающая при уменьшении
, не столь очевидна. Ведь в этом случае в (1) будут уменьшаться и уменьшаемое и вычитаемое.
Так, при
существует многогранник, имеющий одну 1007-угольную и 1009 треугольных граней. Впрочем, для того, чтобы понять, что у него больше диагоналей, чем вышеописанный, даже не нужно прибегать к формуле (1). Ведь, чтобы получить новый многогранник из предыдущего, достаточно малым шевелением:
а) перегнуть четырехугольные грани по диагонали (при этом добавятся две грани, два ребра и две диагонали);
б) спрямить одну из сторон 1008-угольного основания (при этом уйдут одна вершина, одна грань, два ребра и одна диагональ).
Итого, у нового многогранника получится
диагоналей.
Но уже следующее уменьшение
на 1 приведет к лавинообразному росту
. В самом деле, пусть
. Тогда наибольшее возможное значение
равно 1004 (иначе просто некуда будет "впихнуть" необходимое количество граней и ребер). Остальные 1010 грани - треугольники ((см. соответствующий граф на рисунке). Для такого многогранника формула (1) дает
.
При дальнейшем уменьшении
наибольшее возможное
убывает более быстрыми темпами и, следовательно,
растет. Так, при наименьшем возможном
, равном 675, наибольшее
будет 5, а
.
ОбсуждениеПодзаголовок "От двух до пяти", смутивший одних и вдохновивших других марафонцев, случайно достался этой задаче в наследство от ММ208.
Судя по присланным решениям, ММ218 оказалась достаточно сложной. Я же рассматривал ее, как весьма простую. По-видимому, это следствие того, что данную задачу я поставил уже после того, как исследовал вопросы о количестве диагоналей многогранников с фиксированным количеством вершин (граней). В частности, к этому времени я уже знал (и умел доказывать), что для минимизации количества диагоналей надо максимизировать число сторон самой большой грани.
Чтобы понять, насколько по-разному воспринимали сложность задачи участники и ведущий достаточно сравнить авторское решение с решением Владислава Франка, в котором Влад долго и скрупулезно обосновывает... неверный ответ
Сразу отмечу (а то, ведь, не каждый осилит несколько страниц), что в решении Влада есть и верный ответ, но Влад предпочел сохранить в итоговом варианте весь тернистый путь к нему.
Изначально я планировал давать 5 баллов за решения, в которых будут указаны многогранники с 1004 и 1005 диагоналями и приведены (возможно, не идеально строгие, но убедительные) соображения, подтверждающие невозможность меньшего числа диагоналей. Т. е. близкие к тому, что приведено мной. Но в процессе изучения решений участников, я слегка персмотрел эти критерии в сторону увеличения призовых баллов. Я старался не замечать откровения типа
По крайней мере, при оценивании.
Разумеется, число 2017 не особенное по отношению к ММ218. Важна лишь его нечетность. Мне понравилось, что формула
возвращает наименьшее возможное количество диагоналей многогранника с нечетным числом ребер для всех без исключения допустимых значений
и дает заведомо бессмысленные значения для тех
, для которых не существует многогранников. Многие другие формулы, связанные с количеством диагоналей многогранников, допускают исключения для малых значений параметров.
НаградыЗа решение ММ218 участникам начислены следующие призовые баллы:
Владислав Франк, Олег Полубасов и Анатолий Казмерчук - по 8;
Владимир Чубанов - 6;
Виктор Филимоненков и Владимир Дорофеев - по 4.
Эстетическая оценка задачи - 4.2 балла