===========ММ239===============ММ239 (10 баллов)
Существует ли выпуклый многогранник, у которого:
a) не менее половины граней семиугольники;
b) более половины граней семиугольники;
с) не менее половины граней восьмиугольники;
d) более половины граней восьмиугольники;
e) не менее половины граней девятиугольники?
Примечание: Если у вас получается, что ответ на пункт <а> отрицательный, а на пункт <b> - положительный, подумайте еще.
РешениеПривожу решения Виктора Филимоненкова, Анатолия Казмерчука, Владимира Чубанова и vpb.
(Решение Владимира Чубанова)
ММ239Существует ли выпуклый многогранник, у которого:
a) не менее половины граней семиугольники;
b) более половины граней семиугольники;
с) не менее половины граней восьмиугольники;
d) более половины граней восьмиугольники;
e) не менее половины граней девятиугольники?
Эстетическая оценка 5 баллов. Мне нравятся такие задачи, правда, эта сильно пересекается с позапрошлым марафоном.
__________
Ответы: a) -- d) да, e) нет.
Решение.
Решение основано на уже упоминавшемся в марафонах неравенстве

Здесь

-- число

-угольных граней. Равенство получается с применением формулы Эйлера при подсчёте рёбер, вершин и граней простого многогранника (в каждой вершине которого сходится 3 ребра). Если в какой-то из вершин сходится более трёх рёбер, равенство превращается в неравенство. Вывод (1) я не буду давать, поскольку и я, и другие участники уже давали его в одном из прошлых марафонов.
Сразу заметим, что данное неравенство очевидно несовместимо с п. e). С остальными пунктами противоречий нет и результат можно получить из теоремы Эберхарда, но лучше построить подтверждающие примеры.
Для п. a) дадим простой умозрительный пример: обрежем немного все вершины куба, кроме двух диагональных. Тогда все 6 граней куба станут 7-угольными и добавится ещё 6 треугольных граней. В этом случае неравенство (1) становится равенством и можно заметить, что многогранник с меньшим (меньше 12) количеством граней не может удовлетворять п. a).
Для п. b) приведём ещё один явный пример. На рисунке ниже кружочки обозначают место среза вершины, образующее 3-угольную грань. Количество 7-угольных граней в данном примере равно 15, количество 3-угольных -- 11, и 6-угольных -- 3.

Для п.п. c) и d) приведём один пример. Многогранник на рисунке получен пересечением двух 8-угольных пирамид. Если каждую вершину в нём немного обрезать плоскостью, как в примере выше, получим

8-угольных граней и 16 треугольных.

Для произвольных

максимально возможную долю

в общем количестве граней легко можно вычислить, используя теорему Эберхарда, утверждающую, что существует простой многогранник для любого набора

, удовлетворяющего равенству в (1). Следовательно, (недостижимый) супремум возможной доли

составляет

. Для

супремум равен 1 (на последовательности фуллеренов, которые могут иметь произвольно большое количество 6-угольных граней при 12 пятиугольных). При

существуют многогранники, имеющие только

-угольные грани.
(Решение vpb)
ММ239Для выпуклого многогранника

и натурального числа

пусть

--- отношение числа граней

, являющихся

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

. Пусть

,

,

--- числа вершин, ребер, граней соответственно. По формуле Эйлера

. Также

.
Оценим

. Имеем

, где

--- число

-угольников,

--- прочих граней. Таким образом,

,

. Ясно, что

, откуда

Значит

. Подставляя оценки для

и

в формулу Эйлера, находим

, откуда

,

,

,

,

.
QED
Для доказательства второго утверждения сначала рассмотрим некоторый "многогранник" на плоскости (т.е. разбиение плоскости на выпуклые многоугольники).
Пусть

--- некоторая плоскость. Пусть

--- (однозначно определенное
с точностью до движения) разбиение плоскости на правильные 6-угольники с ребром длины

.
Пусть

--- множество всех вершин

.
Лемма. Для каждого
существует такое подмножество
, что ровно
вершин каждого шестиугольника из
принадлежат
. Доказательство. При

, очевидно,

,

. При

предоставляем найти

читателю, нарисовав картинку (

будет периодическим). При

можно взять в качестве

дополнения

,

соответственно. QED
Для

определим некоторое разбиение плоскости на треугольники и (неправильные)

-угольники (неправильные), обозначим его

. Именно, возьмем разбиение

, и каждую вершину

(где

) заменим на небольшой треугольник (детальное описание такой замены опустим).
Ясно, что в разбиении

каждый

-угольник граничит с

треугольниками, а каждый треугольник с тремя

-угольниками. Поэтому асимптотическое отношение числа

-угольников к числу треугольников составляет

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

, и ограничимся рассмотрением тех многоугольников разбиения, которые целиком лежат внутри окружности, то указанное отношение стремится к

, когда

. Поэтому доля

-угольников среди всех граней разбиения стремится к

, что и нужно.
Теперь надо "перенести" описанную конструкцию в пространство. Будем считать плоскость

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

, обозначим ее

. Пусть

--- точка касания,

--- противоположная точка сферы ("южный" и "северный" полюса). Пусть

--- (обратная) стереографическая проекция, т.е.

--- это точка пересечения

с отрезком

, для любой

. Хорошо известно, что при стереографической проекции окружности на плоскости соответствуют окружностям на сфере.
Пусть

--- круг радиуса

с центром в

;

--- образы на сфере тех точек из

, которые лежат в

. Наконец, пусть

--- выпуклая оболочка

в пространстве.
Лемма. Пусть
--- некоторый шестиугольник разбиения
такой, что
;
--- его вершины, и
. Тогда
лежат в одной плоскости, и
--- грань для
, причем
--- вершины этой грани. Доказательство. 
--- правильный шестиугольник, значит он вписан в некоторую окружность

.

--- окружность на

, значит, лежит в некоторой плоскости

. Значит, все

.
Плоскость

делит

на две части, а именно, внутренность и внешность окружности

. Соответствующие части на

--- это внутренность и внешность окружности

. Однако ни одна вершина из

не лежит внутри

. Значит, все вершины из

, и тем более

, лежат по одну сторону от

. При этом на

лежат только

. Значит, их выпуклая оболочка --- это грань многогранника

(и сами они --- в точности вершины этой грани).
QED
В ситуации, описанной в лемме, будем обозначать

через

.
Следствие. Пусть
. Тогда грани в
, содержащие
--- это три шестиугольника (и других граней нет). Доказательство. Пусть

,

,

--- три шестиугольника

, содержащие

. Тогда все они лежат внутри

. Значит

--- грань для

, содержащая

. Поскольку

и

имеют общее ребро, то

и

имеют общее ребро. Но, поскольку каждые две из трех граней

имеют общее ребро, других граней, содержащих

, нет. QED
Таким образом, мы видим, что в окрестности всех вершин, за исключением вершин

, для которых

,

устроено комбинаторно так же, как

. Всего

имеет порядка

вершин, ребер и граней. А "исключительных" вершин, очевидно, порядка

(откуда легко следует, что "нехороших" ребер и граней тоже

).
Теперь мы усечем многогранник

в окрестностях некоторых вершин. А именно, в окрестностях вершин

, для которых

. Довольно понятно, что полученный многогранник содержит столько же

-угольников и треугольников, сколько разбиение

внутри круга

, с точностью до

. А также, возможно, есть

других граней, кроме треугольников и

-угольников. Отсюда следует, что

, чем теорема и доказана.
QED
Обсуждение Ровно в половине всех присланных (и всех приведенных) решений авторы обошлись без картининок.
Чтобы восполнить этот пробел, приведу пару своих картинок (зря, чтоли рисовал?).
Первый рисунок иллюстрирует ответы сразу к трем пунктам задачи: a), b), c).
Отрезав от додекаэдра красные вершины, получим многогранник в котором более (а значит, и не менее) половины граней являются семиугольниками.
Если же наоборот, оставить красные вершины, а остальные отрезать, получим многогранник, в котором ровно половина граней - восьмиугольники.

На втором рисунке приведен граф многогранника с вектором граней (28,0,0,4,0,36), обосновывающий положительный ответ к пункту d).

ММ239 (как и ММ235) - это отголосок XXII Марафонского конкурса, посвященного данной тематике. Участники, пропустившие тот конкурс, вынуждены были переотрывать утверждения типа Теоремы Эберхарда etc (конечно, можно было просто найти нужные результаты в сети, но наши конкурсанты не ищут легких путей

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

) поощрялось дополнительными баллами. В случае
vpb, это поощрение скомпенсировалось сбавкой за штейнеровское отношение к читателю

. (Каюсь, сам я работ Якоба Штейнера в первоисточнике не читал, но, говорят, он свои сугубо геометрические выкладки вообще не снабжал чертежами.)
Остальные изъятия сделаны либо за отсутствие примеров на некоторые пункты, либо за присутствие примеров с невозможными многогранниками (с нецелым количеством ребер

)
Волшебное превращение восьмиугольных граней в семиугольные (при склейке по общей треугольной грани) я оценивать не стал
НаградыЗа решение задачи ММ239 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 12;
Владимир Чубанов - 11;
vpb - 10;
Константин Шамсутдинов - 10;
Виктор Филимоненков - 9;
Владислав Франк - 6.
Эстетическая оценка задачи - 4.8 балла