Обсуждение и разбор марафонских задач

[VAL]

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

ММ212 (4 балла)

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

Решение

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

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

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

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

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

Обсуждение

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

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

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

Награды

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

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

[grizzly]

Не критики ради, а с целью поделиться найденным знанием, прокомментирую:

Олег Полубасов по поводу формулы 2V-10 писал(а):

Примечание. Никто не утверждает, что на меньшее число тетраэдров -- нельзя.

Здесь, стр.678, утверждается, что для достаточно больших $V$ формула точна и предполагается в качестве гипотезы, что формула точна для все $V>12.$ Насколько мне известно, воз и ныне там (последнее подтверждение видел в обзоре 2006 г.). Но думаю, 2016 достаточно удобное число для построения явного контрпримера.

[Masik]

grizzly в сообщении #1152139 писал(а):

Олег Полубасов по поводу формулы 2V-10 писал(а):

Примечание. Никто не утверждает, что на меньшее число тетраэдров -- нельзя.

Здесь, стр.678, утверждается, что для достаточно больших $V$ формула точна и предполагается в качестве гипотезы, что формула точна для все $V>12.$ Насколько мне известно, воз и ныне там (последнее подтверждение видел в обзоре 2006 г.). Но думаю, 2016 достаточно удобное число для построения явного контрпримера.

Не знаю, что Вы имеете в виду под контрпримером. Может, 2015-угольная пирамида подойдёт.

[grizzly]

Masik в сообщении #1152622 писал(а):

Не знаю, что Вы имеете в виду под контрпримером.

Я имею в виду пример 2016-гранника, показывающего, что оценка снизу, которую Вы указали в своём ответе, не может быть улучшена.

Masik в сообщении #1152622 писал(а):

Может, 2015-угольная пирамида подойдёт.

Нет, это тривиальный пример существования, который лично мне представляется менее интересным, чем открытая (?) проблема. Но я понял, что в Примечании подразумевался квантор существования, а не всеобщности.

[VAL]

===========ММ213===============

ММ213 (4 балла)

1. Пусть $H = \{h_1, h_2, \dots h_f\}$, где $f$ - количество граней, а $h_i$ - число сторон i-й грани. Какое наименьшее значение может принимать $f-|H|$ ?
2. Пусть $g_i$ означает число i-угольных граней многогранника для каждого значения $i$ . Могут ли все $g_i$ не превышать 2?

Решение

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

(Решение Игоря Ханова)

ММ213
1. Пусть $ H = \{h_1, h_2, \dots h_{f}\} $, где $ f $ - количество граней, а $ h_{i} $ - число сторон $ i $-й грани. Какое наименьшее значение может принимать $f-|H|$ ?
2. Пусть $ g_{i} $ означает число $ i $-угольных граней многогранника для каждого значения $ i $ . Могут ли все $ g_{i} $ не превышать 2?
Решение
1. Рассмотрим грань с наибольшим количеством сторон и обозначим это количество через $ n $. К этой грани прилегает ровно $ n $ других и их общее количество $ n+1\leq f $. Это значит, что все элементы множества $ H $ удовлетворяют неравенству $ 3\leq h_{i}\leq f-1 $. Следовательно, $ H $ содержит не более $ f-1-3+1=f-3 $ элементов и $ f-|H|\geq 3 $. Данная оценка достигается, например, для треугольной призмы.
2. Да, могут. Для примера возьмем пятиугольную пирамиду и разрежем ее плоскостью, проходящей через ребро основания. Гранями нижней части будут служить два треугольника, два четырехугольника и два пятиугольника. (Также здесь можно добавить, что из первого пункта следует тот факт, что все $ g_{i} $ не могут не превышать 1, поскольку тогда бы $ f-|H|=0 $).

Обсуждение

Задача ММ213 практически не вызвала затруднений у участников. Но, все же, одно затруднение было. Не все сразу поняли смысл обозначения $|H|$.
Отмечу также, что некоторые участники прошли мимо очевидного обоснования соотношения $f-|H|>2$ и, как нормальные герои, пошли в обход.

Награды

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

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

[VAL]

===========ММ214===============

ММ214 (4 балла)

1. Все грани многогранника - n-угольники. При каких n это возможно?
2. При каком наименьшем числе граней существует многогранник, все грани которого пятиугольны?

Решение

В качестве образца типового решения приведу то, которое прислал Виктор Филимоненков. Решения с обобщениями традиционно представлены Олегом Полубасовым и Анатолием Казмерчуком.

Обсуждение

Для решения ММ214 практически все участники в той или иной форме перевывели часть, так называемой, теоремы Эберхарда:
Для любого многогранника справедливо соотношение $\sum_{i=3}^n g_i(6-i) \ge 12$, где $g_i$ - количество i-угольных граней, а $n$ - максимум числа сторон в гранях. Причем это неравенство обращается в равенство тогда и только тогда, когда многогранник является простым (степень каждой вершины равна 3).
Кроме того в теореме Эберхарда утверждается, для любого набора $g_i$, удовлетворяющего соотношению $\sum_{i=3}^n g_i(6-i) = 12$, при подходящем значении $g_6$ найдется соответствующий многогранник.

Поскольку большинство марафонцев получили требуемые соотношения еще при решении предыдущих задач конкурса, ответы на ММ214 получились совсем короткими.

Олег Полубасов и Анатолий Казмерчук заинтересовались естественным вопросом о возможных количествах граней многогранников, все грани которых имеют поровну сторон. При $n=3$ ответ на этот вопрос тривиален. При $n=4$ ответ был получен при обобщении ММ211. Поэтому интересен лишь случай $n=5$.

Вопрос о максимальной возможной степени вершин рассматриваемых многогранников показался мне несколько "притянутым за уши" к MM214.

Награды

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

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

[grizzly]

К обсуждению задачи ММ213.

VAL в сообщении #1156463 писал(а):

Для любого многогранника справедливо соотношение $\sum_{i=3}^n g_i(6-i) \ge 12$

Это соотношение меня заинтересовало при рассмотрении вопроса, который поднял в своём решении Анатолий Казмерчук. Я приведу здесь полную формулировку вопроса:

Пусть для некоторого натурального $m\ge 3$ и для каждого $n\ge 3$ среди граней многогранника имеется не более чем $m$ $n$-угольников. Сколько сторон может иметь самая многосторонняя грань такого многогранника?

UPD 04.10.2016. См. уточнённую формулировку в моём сообщении ниже.

Имея на вооружении процитированное неравенство, легко можно получить оценку сверху: $N_{\max}\le 5m-3$. На глаз заметно, что от эта оценка может быть сколько-то уменьшена, но я не вижу, как уменьшить множитель 5.
С другой стороны, очень просто построить руками пример для оценки снизу: $N_{\max}\ge 2m+1$. Думаю, эту тоже мог бы чуть улучшить, но не множитель 2.
Дальше я не смог продвинуться и продолжил поиски в сети. Впрочем, поиск тоже ничего не дал (хотя я и увидел много интересного), скорее наоборот -- похоже на то, что все подобные задачи довольно сложны и не имеют пока окончательного решения.

Но может кто посоветует, как улучшить приведенные мной простые оценки?

[VAL]

Наверное, мне надо было написать об этом в преамбуле к конкурсу.
Но, как говорится, лучше поздно чем никогда.

Предлагаю на протяжении оставшейся части конкурса использовать следующие обозначения:
$v, e, f$ — количество вершин ребер и граней многогранника соответственно (от vertices, edges и faces).
Прочие обозначения оговаривать по мере их введения. И учитывать такие договоренности.

В противном случае возникает путаница.

Например, в предыдущем сообщении grizzly цитирует формулу, приведя которую я явно оговорил, что понимается под $n$:

VAL в сообщении #1156463 писал(а):

$n$ - максимум числа сторон в гранях

Однако в вопросе grizzly вместо $n$ используется $N_{max}$, а $n$ имеет уже иной смысл.

[grizzly]

VAL в сообщении #1157103 писал(а):

Однако в вопросе grizzly вместо $n$ используется $N_{max},$ а $n$ имеет уже иной смысл.

Да, запутал я немного, поэтому придётся ещё уточнить.

Я лучше переформулирую тогда всё заново:

Пусть $m\ge 3, m\in \mathbb N$. Рассмотрим многогранники, у которых количество $i$-угольных граней не превышает $m$ для каждого $3\le i\le n$ (здесь $n$ -- максимум числа сторон в гранях). Задача: найти / оценить $n_{\max}(m)$ -- максимально возможное значение $n$ среди всех многогранников, удовлетворяющих заданным условиям при фиксированном $m$.

Для тех, кто не в танке, уточню также, что речь идёт только о выпуклых многогранниках в $\mathbb R^3.$

[Masik]

grizzly в сообщении #1157111 писал(а):

Я лучше переформулирую тогда всё заново:
Пусть $m\ge 3, m\in \mathbb N$. Рассмотрим многогранники, у которых количество $i$-угольных граней не превышает $m$ для каждого $3\le i\le n$ (здесь $n$ -- максимум числа сторон в гранях). Задача: найти / оценить $n_{\max}(m)$ -- максимально возможное значение $n$ среди всех многогранников, удовлетворяющих заданным условиям при фиксированном $m$.

Проще говоря: пусть в выпуклом многограннике количество граней каждого размера не превышает $m$. Найти максимально возможный размер грани $n$.
Ясно, что функция неубывающая. Известно, что $n(2) = 6$.
Обозначим: $f$ - число граней, $v$ - вершин, $e$ - рёбер, $h_i$ - размер $i$-й грани.
Назовём величину $w_i = h_i - 6$ весом $i$-й грани. Тогда $\sum_{i=1}^f{(h_i-6)}=2e-6f\leqslant -12$.
Значит, чтобы как можно больше увеличить размер грани, надо использовать все грани отрицательного веса, но последних не более $3m$ с суммой $((3-6) + (4-6) + (5-6))m = -6m$. Следовательно, сумма весов всех граней положительного веса не может превышать $6m - 12$.
Пусть число граней положительного веса равно $F + 1$. Размер любой грани должен быть меньше общего числа граней, поэтому $n \leqslant f - 1 = 4m + F$ (учитываем $m$ шестиугольных граней).
Сумма весов всех граней положительного веса $W \geqslant F + n - 6$, $W \leqslant 6m - 12$. $\Rightarrow n \leqslant 6m - F - 6$.
Итого, имеем два ограничения.
$n \leqslant 4m + F$.
$n \leqslant 6m - F - 6$.
Пересечение этих ограничений $4m + F = 6m - F - 6$ происходит при $F = m - 3$.
Пусть $F = m - 3$ ($m-3$ семиугольников и одна грань размера $n$).
Тогда $n \leqslant 5m - 3$, $m \geqslant 3$.
Полагаю, что соответствующие многогранники должны существовать.

[grizzly]

Masik в сообщении #1157934 писал(а):

Тогда $n \leqslant 5m - 3$, $m \geqslant 3$.

Спасибо. Эти рассуждения один в один совпали с моими. Вывод, естественно, тоже (другое дело уметь это так хорошо записать):

grizzly в сообщении #1157062 писал(а):

можно получить оценку сверху: $N_{\max}\le 5m-3$.

Masik в сообщении #1157934 писал(а):

Полагаю, что соответствующие многогранники должны существовать.

Конечно же нет. В принципе не могут. Достаточно представить себе, как выглядит эта "корона Российской Империи", когда на основание прилеплены всякие там семиугольники :) Да хотя бы $m=3$ посмотреть и станет понятно, насколько дальше всё хуже. Поэтому меня всё еще интересует хоть какое-то улучшение множителя предложенной ранее оценки:

grizzly в сообщении #1157062 писал(а):

С другой стороны, очень просто построить руками пример для оценки снизу: $N_{\max}\ge 2m+1$. Думаю, эту тоже мог бы чуть улучшить, но не множитель 2.

[VAL]

grizzly в сообщении #1157950 писал(а):

grizzly в сообщении #1157062 писал(а):

можно получить оценку сверху: $N_{\max}\le 5m-3$.

Masik в сообщении #1157934 писал(а):

Полагаю, что соответствующие многогранники должны существовать.

Конечно же нет. В принципе не могут.

Может, и не могут...
Но для $m=3$, я подходящий многогранник беспринципно построил

[grizzly]

VAL в сообщении #1157954 писал(а):

Но для $m=3$, я подходящий многогранник беспринципно построил

Снимаю шляпу :) И мои извинения Masik. Что ж, пространственное воображение меня вновь подводит.
Нельзя вывесить здесь картинку, раз уж есть готовая?

[VAL]

Вот соответствующий граф:

[grizzly]

VAL, Masik
Красиво, спасибо!

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

Оставлю, пожалуй, здесь эту ссылку для тех, кому будет интересно. Там (см. также гиперссылки) лучшая библиография по (около) этой теме [англоязычных источников] из того, что мне попадалось на глаза.