Математический факультетИнформация для студентовЭлектронная библиотека
Карта сайтаКарта сайта
Недавние измененияНедавние изменения
ПоискПоиск
  
Вы посетилиВы посетили
История страницыИстория страницы
  
Вход/выходВход


Содержание

ММ212

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

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

Решение

Приведу решения Олега Полубасова, Анатолия Казмерчука и

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

Доказательство.
Каждую грань многогранника разделим диагоналями на непересекающиеся треугольники. Это, очевидно, просто. Все построенные диагонали условно присовокупим к множеству рёбер. Зафиксируем одну из вершин; далее выберем 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 балла


 

 


Страница: [[marathon:problem_212]]

marathon/problem_212.txt · Последние изменения: 2016/09/26 09:32 — letsko
Powered by DokuWiki  ·  УКЦ ВГПУ 2006