===========ММ212===============ММ212 (4 балла)
Доказать, что любой многогранник, имеющий 2016 вершин, может быть разрезан на 4030 тетраэдров.
РешениеПривожу решения Олега Полубасова, Анатолия Казмерчука и Владимира Чубанова:
(Решение Владимира Чубанова)
Доказательство.Каждую грань многогранника разделим диагоналями на непересекающиеся треугольники. Это, очевидно, просто. Все построенные диагонали условно присовокупим к множеству рёбер. Зафиксируем одну из вершин; далее выберем 3 другие вершины одной из треугольных граней, образованных всеми настоящими и новыми рёбрами (далее T-грани). Очевидно, что фиксированная вершина образует с выбранными тремя тетраэдр. Далее перебираем все аналогичные тетраэдры, рассматривая все T-грани. Легко показать, что набор таких тетраэдров образует разбиение многогранника, а именно:
-- тетраэдры не пересекаются;
-- любая точка многогранника принадлежит одному из тетраэдров.
Теперь необходимо их сосчитать. Будем без доказательства использовать формулу Эйлера
(в данной формуле буквами последовательно обозначены рёбра, вершины, грани) -- эту формулу мы применяем к изначально заданному многограннику.
Нужно также учесть новые рёбра и образованные ими T-грани. С одной стороны, каждое новое ребро добавляет одну грань, поэтому с учётом всех рёбер и T-граней формула останется такой же. С другой стороны, мы можем непосредственно пересчитать все T-грани и рёбра (новые со старыми): каждая T-грань даёт 3 ребра, каждое ребро в этом подсчёте учитывается дважды. Следовательно, получим
. Приводя подобные, имеем:
.
Подставив данное в условии задачи число вершин, получим ограничение сверху на количество тетраэдров в разбиении:
. Поскольку в образовании некоторых T-граней участвует фиксированная вершина, реальная оценка будет чуть меньше -- как минимум на 3. Ну да не беда: уже полученный тетраэдр всегда можно разбить на несколько других тетраэдров добавляя новые вершины. Следовательно, можно получить и требуемое разбиение в 4030 тетраэдров.
ОбсуждениеПочти все остальные участники (чьи решения не попали в число приведенных) выбирали общую вершину внутри многогранника. В результате у них получилась более грубая оценка снизу для возможного числа многогранников. Впрочем, и ее вполне хватило для решения.
Некоторые участники высказали свои предположения относительно происхождения числа 4030 в условии. Как человек давно и хорошо знающий ведущего Марафона, могу подтвердить: гипотеза о том, что число 4030 возникло в результате банальной арифметической ошибки, вполне реалистична. Но в данном случае она, все же, не верна. А вот версия Дмитрия Пашуткина "это попытка ведущего запутать решающих:)" ближе к истине. Я долго выбирал между вариантами 4028 (общая вершина тетраэдров внутри многогранника) и 4025 (с учетом смещения общей вершины тетраэдров в одну из вершин многогранника и наиболее очевидных последствий такого смещения), пока не остановился на варианте... 4030.
Приведенная в решении Анатолия Казмерчука нижняя оценка количества тетраэдров, на которые можно разрезать многогранник, имеющий
вершин, может быть получена проще: Первый тетраэдр содержит 4 вершины многогранника, а каждый последующий еще, как минимум, одну. Итого получается не меньше
тетраэдров. Рассмотрение тетраэдров, вершины которых не состоят только из вершин исходного многогранника, приводит только к увеличению количества тетраэдров разбиения.
НаградыЗа правильное решение задачи ММ212 и получение некоторых дополнительных оценок Анатолий Казмерчук получает 7 призовых баллов, а Олег Полубасов - 6 призовых баллов. За правильное решение ММ212 Василий Дзюбенко, Игорь Ханов, Владимир Чубанов, Владислав Франк, Виктор Филимоненков и Дмитрий Пашуткин получают 4 призовых балла, а Владимир Дорофеев (его решение имеет небольшой недочет) - 3 призовых балла.
Эстетическая оценка задачи - 4.3 балла