=====ММ212=====

**Конкурсная задача ММ212** (4 балла)

Доказать, что любой многогранник, имеющий 2016 вершин, может быть разрезан на  4030 тетраэдров.

**Решение**

Приведу решения {{:marathon:mm212_polubasoff.pdf|Олега Полубасова}}, {{:marathon:kazmerchuk_pr_212.docx|Анатолия Казмерчука}} и 

**Решение Владимира Чубанова**

**Доказательство.**\\
Каждую грань многогранника разделим диагоналями на непересекающиеся треугольники. Это, очевидно, просто. Все построенные диагонали условно присовокупим к множеству рёбер. Зафиксируем одну из вершин; далее выберем 3 другие вершины одной из треугольных граней, образованных всеми настоящими и новыми рёбрами (далее T-грани). Очевидно, что фиксированная вершина образует с выбранными тремя тетраэдр. Далее перебираем все аналогичные тетраэдры, рассматривая все T-грани. Легко показать, что набор таких тетраэдров образует разбиение многогранника, а именно:\\
-- тетраэдры не пересекаются;\\
-- любая точка многогранника принадлежит одному из тетраэдров.

Теперь необходимо их сосчитать. Будем без доказательства использовать формулу Эйлера e+2 = v+f (в данной формуле буквами последовательно обозначены рёбра, вершины, грани) -- эту формулу мы применяем к изначально заданному многограннику.\\ 
Нужно также учесть новые рёбра и образованные ими T-грани. С одной стороны, каждое новое ребро добавляет одну грань, поэтому с учётом всех рёбер и T-граней формула останется такой же. С другой стороны, мы можем непосредственно пересчитать все T-грани и рёбра (новые со старыми): каждая T-грань даёт 3 ребра, каждое ребро в этом подсчёте учитывается дважды. Следовательно, получим f = 2e/3. Приводя подобные, имеем: f = 2v-4. 

Подставив данное в условии задачи число вершин, получим ограничение сверху на количество тетраэдров в разбиении: 2·2016 - 4 = 4028. Поскольку в образовании некоторых T-граней участвует фиксированная вершина, реальная оценка будет чуть меньше -- как минимум на 3. Ну да не беда: уже полученный тетраэдр всегда можно разбить на несколько других тетраэдров добавляя новые вершины. Следовательно, можно получить и требуемое разбиение в 4030 тетраэдров.

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

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

Некоторые участники высказали свои предположения относительно происхождения числа 4030 в условии. Как человек давно и хорошо знающий ведущего Марафона, могу подтвердить: гипотеза о том, что число 4030 возникло в результате банальной арифметической ошибки, вполне реалистична. Но в данном случае она, все же, не верна. А вот версия Дмитрия Пашуткина "это попытка ведущего запутать решающих:)" ближе к истине. Я долго выбирал между вариантами 4028 (общая вершина тетраэдров внутри многогранника) и 4025 (с учетом смещения общей вершины тетраэдров в одну из вершин многогранника и наиболее очевидных последствий такого смещения), пока не остановился на варианте... 4030.

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

**Награды**

За правильное решение задачи ММ212 и получение некоторых дополнительных  оценок Анатолий Казмерчук получает 7 призовых баллов, а Олег Полубасов - 6 призовых баллов. За правильное решение ММ212 Василий Дзюбенко, Игорь Ханов, Владимир Чубанов, Владислав Франк, Виктор Филимоненков и Дмитрий Пашуткин получают 4 призовых балла, а Владимир Дорофеев (его решение имеет небольшой недочет) - 3 призовых балла.

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