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

[Masik]

Здесь главное, что известна структура многогранника: $m$ граней размера 3, $m$ граней размера 4, $m$ граней размера 5, $m$ граней размера 6, $m-3$ грани размера 7 и одна грань размера $5m-3$.

[VAL]

Построил 18-гранник для $m=4$. (Всего со 2-й попытки, быстрее чем 13-гранник для случая $m=3$.)

У меня есть книжка: Grünbaum, B., Convex Polytopes, 2nd. edition, Springer-Verlag, New York, 2003 (first edition, 1967, Wiley-Interscience) из списка по ссылке grizzly.
Кому интересно пишите в личку.

PS: Пока формулировал уже и случай $m=6$ появился!
А для $m=3$ я пытался построить симметричную картинку. Но у меня вышла только кривая

[Masik]

Если фигуру, показанную на рис. 1, вклинить между двух пятиугольников (рис. 2), то один из пятиугольников превратится в шестиугольник, а другой - в семиугольник (рис. 3).



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

[VAL]

===========ММ215===============

мм215 (4 балла)

На какое наименьшее количество тетраэдров можно разрезать шестиугольную призму?

Решение

Привожу решения Виктора Филимоненкова, Дмитрия Пашуткина и Анатолия Казмерчука.

Обсуждение

Эта задача оказалась первой в нынешнем конкурсе, вызвавшей затруднение сразу у нескольких участников.
Несколько неожиданно для меня даже разрезание призмы на 10 тетраэдров удалось найти не всем.
Более ожидаемыми были затруднения с доказательством минимальности 10 тетраэдров.
Авторское решение выглядело примерно так:
В верхней и нижней гранях лежат основания не менее чем 8 тетраэдров разбиения. Их суммарный объем - не более $\frac23$ объема призмы. Однако объем одного тетраэдра, содержащегося в шестиугольной призме, не может составлять треть объема призмы. Ну и предъявить разрезание на 10 тетраэдров.
При этом не заморачивался с доказательством утверждения, выделенного курсивом, понадеявшись, что это сделают конкурсанты (и они, в целом, не подвели ).
Кроме того, я надеялся, что участники придумают и другие интересные обоснования минимальности 10 тетраэдров, не связанные с подсчетом объемов.
Но здесь оказалось все не так просто. Другие обоснования были предложены. но либо недостаточно строгие, либо слишком путаные, либо то и другое вместе.
В частности, я испытывал затруднения в оценке строгости решения Дмитрия Пашуткина. В нем вызывает вопросы обоснованность фразы:
"Оставшаяся часть призмы разрезана гранями восьми тетраэдров с гранями на основаниях, и оставшийся многогранник будет иметь более четырех граней." . После некоторых сомнений я решил исходить из "презумпции невиновности", т.е. считать, что Дмитрий не привел подробностей лишь на том основании, что они ему очевидны.

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

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

В связи с рассмотрением ММ215 у меня возник интересный вопрос.
Будем проводить "тетраэдризацию" многогранников по следующим правилам:
За один шаг можно разрезать многогранник (исходный или полученный на одном из предыдущих шагов и рассматриваемый отдельно) плоскостью, проходящей не менее чем через 3 вершины многогранника. процесс продолжаем до тех пор, пока исходный многогранник не разобьется на тетраэдры.

Легко видеть, что всякая n-угольная пирамида разобьется на $n-2$ тетраэдра.
Для куба (четырехугольной призмы) имеем уже два возможных ответа: 5 и 6.
Для треугольной бипирамиды возможные ответы 2 и 4 уже не являются соседними числами.
Таким образом, у каждого многогранника возникает любопытные характеристики: минимальное количество тетраэдров (в "тетраэдризации", проведенной по вышеописанным правилам); максимальное количество тетраэдров; набор возможных количеств тетраэдров...
Или, все же, не у каждого?

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

Может быть, многогранники делятся на "тетраэдризируемые" за конечное число шагов и те, для которых вышеописанный процесс не всегда (или даже всегда не) сходится?


Награды

За решение и обобщение задачи ММ215 участникам начислены следующие призовые баллы:
Анатолий Казмерчук - 7;
Владислав Франк и Олег Полубасов - по 5;
Владимир Чубанов, Виктор Филимоненков и Дмитрий Пашуткин - по 4 балла;
Дмитрий Курашкин - 3;
Василий Дзюбенко - 1.

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

Замечание

Я пока не успел разобраться со всеми выкладками Анатолия Казмерчука при обобщении задачи. Но его формулы для минимального числа тетраэдров, на которые можно разрезать n-угольную призму, совпали с теми, которые получились у меня и теми, что получил Олег Полубасов.
Поэтому, дабы не томить конкурсантов, я решил опубликовать разбор задачи до окончательного изучения решения Анатолия. Если же в процессе такого изучение всплвет что-то новенькое, я это прокомментирую.

[grizzly]

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

Однако для каждого из кандидатов на роль такой характеристики мне легко удавалось найти пример многогранника и разрезания, после которого эта характеристика возрастает или не меняется.

Для комбинаций характеристик тоже?
Среди этих кандидатов было "количество различных способов разрезания на данном шаге"?

[VAL]

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

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

Однако для каждого из кандидатов на роль такой характеристики мне легко удавалось найти пример многогранника и разрезания, после которого эта характеристика возрастает или не меняется.

Для комбинаций характеристик тоже?

Рассматривал и комбинации.

Цитата:

Среди этих кандидатов было "количество различных способов разрезания на данном шаге"?

А вот это не было. Надо попробовать.

[grizzly]

VAL
Мне прислали на почту пример бесконечного разрезания. В границах моего пространственного воображения похоже на правду. Просьба проверить независимо:

Цитата:

если взять шестигранную призму $ABCDEFA'B'C'D'E'F'$ и первый разрез провести через $A'CE$, получив новые вершины $B''$ и $F''$ (отбросить часть с $B$ и $F$), а потом разрезать через $B''F''D$ и отбросить часть с $C$ и $E$, то получим тело, которое так же можно резать и дальше (попеременно через $A'C^*E^*$ и $B^*F^*D$).

[VAL]

Только я собрался написать, что предложенная Вами характеристика тоже может не уменьшаться...
Было бы странно, если бы она всегда уменьшалась

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

VAL
Мне прислали на почту пример бесконечного разрезания. В границах моего пространственного воображения похоже на правду. Просьба проверить независимо:

Цитата:

если взять шестигранную призму $ABCDEFA'B'C'D'E'F'$ и первый разрез провести через $A'CE$, получив новые вершины $B''$ и $F''$ (отбросить часть с $B$ и $F$), а потом разрезать через $B''F''D$ и отбросить часть с $C$ и $E$, то получим тело, которое так же можно резать и дальше (попеременно через $A'C^*E^*$ и $B^*F^*D$).

Да, вроде, все проходит!
Я почему-то боялся думать над подобным примером. Мне казалось, что такой многогранник (если он есть) должен быть каким-то монстром... А здесь все вполне обозримо. Более того, практически в рамках ММ215.

PS: А почему пример прислали Вам, а не сюда? Или Вы в другом месте спрашивали?

[grizzly]

(VAL)

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

А почему пример прислали Вам, а не сюда? Или Вы в другом месте спрашивали?

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

[VAL]

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

Для куба (четырехугольной призмы) имеем уже два возможных ответа: 5 и 6.

Это я погорячился
Похоже, уже для куба (четырехугольной призмы) возможен бесконечный процесс.
Так что "тетраэдризируемые" (в смысле, изложенном в обсуждении ММ215) многогранники весьма редки.

[VAL]

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

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

Посмотрел аккуратнее. Не "похоже", а точно.

[VAL]

Срок приема решений ММ216 продлен на сутки, до 24:00 30.10.2016

[VAL]

===========ММ216===============

ММ216 (10 баллов)

Назовем натуральное число n красивым, если наименьшее натуральное число, имеющее ровно n натуральных делителей, кратно n.
1. Доказать, что все праймориалы красивы.
2. Верно ли, что все факториалы красивы?
3. Сколько существует красивых чисел вида $k^7$, где $k$ - некоторое натуральное число?
4. Сколько существует красивых чисел вида $7^k$, где $k$ - некоторое натуральное число?

Решение

привожу решения Владислава Франка и Олега Полубасова.

Обсуждение

Ход 22-го марафонского турнира все более напоминает картину предыдущего: достаточно дружный старт, а к середине начинается выпадение участников.
Остается надеяться, что на этот раз к заключительным задачам притормозившие марафонцы вернутся на дистанцию. Основание для таких надежд есть - ведь все последующие задачи опять про приглянувшиеся большинству марафонцев многогранники.

Так или иначе, на ММ216 получено всего 4 решения. А обоснованный ответ на все пункты задачи имеется и вовсе в двух из них.
Соглашусь, что аккуратные обоснования немного (а если пойти длинным путем то и весьма) муторны.
В то же время, для меня было удивительно, что даже бывалые, искушенные участники (не все, но и не один) не заметили, что в качестве 7-х степеней годятся 14-е, 21-е etc., тем самым, резко усложнив для себя 3-й пункт задачи.

Отмечу, что факториалы степеней двойки (и последующих чисел вплоть до первого простого) не являются красивыми, начиная $8!$, даже если предшествующее степени двойки число является простым числом Мерсенна (как собственно и происходит для 8). Вообще, среди факториалов довольно много некрасивых (в первой тысяче, например, 345) и это совсем не обязательно числа из диапазона $[2^k..p_m-1]$, где $p_{m-1}<2^k<p_m$.

Красивых чисел не было в OEIS. Я восполнил этот пробел - A262981. (а Антон Никонов дополнил, то что я восполнил.)
Назовем наименьшее натуральное число, имеющее ровно $n$ делителей, родительским для $n$ (буду благодарен тому, кто предложит более удачное название). Такие числа приведены в A005179.
Антон Никонов высказал два предположения:
1. Стартуя с произвольного натурального числа и переходя к родительскому, мы рано или поздно доберемся до красивого числа.
Например, $7 \to 64 \to 7560$, и мы пришли к красивому числу.
2. Родительское число красивого числа само красиво.

Исходя из этих предположений Антон ввел примитивные красивые числа: $1,2,6,8,9,18,20,30,45,\dots$

Формулируя ММ216, я надеялся, что получу не предположения 1 и 2, а доказанные утверждения 1 и 2. Увы...
Несмотря на отсутствие доказательства, 1-я гипотеза не вызывает у меня ни малейших сомнений, а вторая кажется весьма правдоподобной.

Еще одно предположение: произведение взаимно простых красивых чисел красиво.

Награды

За решение и обобщение задачи мм216 участникам начислены следующие призовые баллы:
Олег Полубасов - 13:
Владислав Франк - 11;
Антон Никонов - 9;
Анатолий Казмерчук - 6;

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

[Yadryara]

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

Олег Полубасов - 13:
Олег Полубасов - 11;

Ну что ж, заслужил Так бы и писали сразу: 24

[VAL]

Yadryara в сообщении #1164664 писал(а):

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

Олег Полубасов - 13:
Олег Полубасов - 11;

Ну что ж, заслужил Так бы и писали сразу: 24

Боюсь, Влад Франк не согласится.