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

[Yadryara]

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

1. Стартуя с произвольного натурального числа и переходя к родительскому, мы рано или поздно доберемся до красивого числа.
Например, $7 \to 64 \to 7560$, и мы пришли к красивому числу.
2. Родительское число красивого числа само красиво.

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

Ещё я имел в виду более сильную гипотезу.

Если в цепочке появилось красивое число, построенное на базе канонической факторизации, то и все бо́льшие красивые числа можно строить таким же простейшим способом.

Примеры.

С числом $6$ всё просто.

$$6 = 2 \cdot 3 \to 2^2\cdot3 \to 2^2 \cdot3\cdot5 \to 2^4\cdot3^2\cdot5\cdot7 \to 2^6\cdot3^4\cdot5^2\cdot7^2\cdot11\cdot13\cdot17\cdot19 \to ... $$

То бишь

$$6 \to 12 \to 60 \to 5040 \to 293318625600 \to ... $$

Здесь все числа красивы и строятся на базе канонической факторизации.

С числом $8$ сложнее.

$$8 = 2^3 = 2\cdot4 \to 2^3\cdot3 = 2\cdot3\cdot4 \to 2^3\cdot3^2\cdot5 \to 2^4\cdot3^2\cdot5^2\cdot7\cdot11\cdot13 \to ... $$

$$8 \to 24 \to 360 \to 3603600 \to ... $$

Для построения следующего красивого дважды приходится делать замены. Не $8 = 2^3$, а $8 = 2\cdot4$. Не $24 = 2^3 \cdot3$, а $24 = 2\cdot3\cdot4$. Но для $360 = 2^3\cdot3^2\cdot5$ уже замены не нужны и все следующие числа, начиная с $3603600$ строятся лишь с помощью канонической факторизации.

[Masik]

Я пока ещё плохо умею гуглить. Вероятно, поэтому мне не удалось найти в Сети ничего путного на русском языке о минимальных числах, имеющих заданное количество делителей. Кто знает хорошие ссылки, набросайте, пожалуйста, мне В ЛИЧКУ.
Особенно интересуют эффективные алгоритмы нахождения минимального числа, имеющего заданное количество делителей. Какова алгоритмическая сложность этой задачи?
Также, интересно узнать про числа, которые Антон Никонов называет "построенными на базе канонической факторизации" (они не обязаны быть ни красивыми, ни даже минимальными). Есть ли у них официальное название?
A037019

[VAL]

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

мне не удалось найти в Сети ничего путного на русском языке о минимальных числах, имеющих заданное количество делителей. Кто знает хорошие ссылки, набросайте, пожалуйста, мне В ЛИЧКУ.

Протестую! Мне тоже интересно.

Цитата:

Особенно интересуют эффективные алгоритмы нахождения минимального числа, имеющего заданное количество делителей. Какова алгоритмическая сложность этой задачи?

На маленьких числах моя программка считает в миллионы раз быстрее той maple-процедуры, что приведена в OEIS - список из 100 первых элементов A005179 строит за сотую долю секунды.
Но, к сожалению, временная сложность моей программы экспоненциальная (основана на переборе разбиений множества). Поэтому она тормозит уже на поиске минимального числа, имеющего 1024 делителя (который легко делается вручную). Я ей особо не занимался - написал только для ММ216.

Мне очевидно, что специалист, виртуозно владеющий методом ветвей и границ мог резко повысить эффективность программы.
Если интересно, могу прислать код (на maple).

Цитата:

Также, интересно узнать про числа, которые Антон Никонов называет "построенными на базе канонической факторизации" (они не обязаны быть ни красивыми, ни даже минимальными). Есть ли у них официальное название?
A037019

Полагаю, что нет. Иначе оно было бы в OEIS, которую посещает немалое количество специалистов.

PS: Заглянул в abstract статьи Savvopoulou, A.K. & Wedrychowicz, C.M. по ссылке в OEIS. Атворы называют числа $n$, для которых наименьшее натуральное число, имеющее $n$ делителей, есть $A037019(n)$, ординарными. Но, разумеется, это локальное название, действующее в пределах статьи.

[VAL]

В OEIS есть и экстраординарные числа - A072066.
Так что, название не "ординарные" не совсем локальное.

[Yadryara]

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

В OEIS есть и экстраординарные числа - A072066.
Так что, название не "ординарные" не совсем локальное.

Да, эти экстраординарные числа A072066 — те самые, в которых нужно делать замены при поиске красивых. Числа определённого вида. Среди них обязательно должны присутствовать все степени двойки, начиная с 3-й, все степени тройки, начиная с 5-й и другие степени всех простых:

$2^{\ge3},3^{\ge5},5^{\ge12},7^{\ge32},11^{\ge310}, ...$

Прошу прощения, если это банальность.

[VAL]

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

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

В OEIS есть и экстраординарные числа - A072066.
Так что, название не "ординарные" не совсем локальное.

Да, эти экстраординарные числа A072066 — те самые, в которых нужно делать замены при поиске красивых. Числа определённого вида. Среди них обязательно должны присутствовать все степени двойки, начиная с 3-й, все степени тройки, начиная с 5-й и другие степени всех простых:

$2^{\ge3},3^{\ge5},5^{\ge12},7^{\ge32},11^{\ge310}, ...$

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

[VAL]

===========ММ217===============

ММ217 (6 баллов)

Диагонали $AC_1$ и $BD_1$ шестигранника $ABCDA_1B_1C_1D_1$, все грани которого четырехугольны, пересекаются в точке $O$. Могут ли остальные пары диагоналей скрещиваться?

Решение

Привожу решения Олега Полубасова, Анатолия Казмерчука и Дмитрия Пашуткина.
Чуть позже (из-за ограничения на количество вложений) приведу еще пару решений.

Обсуждение

Мои ожидания отчасти сбылись. Некоторые из марафонцев, не приславших ответов на ММ216, вернулись на дистанцию. Но не все. И если некоторые из "невозвращенцев" приучили меня к такому их поведению, выпадая по ходу и из предыдущих конкурсов, то от других я этого не ожидал.

Отмечу момент, не сформулированный явно ни в одном из решений. Если любые две диагонали нашего шестигранника пересекаются, то все они пересекаются в одной точке. Если же пересекаются лишь две или четыре пары диагоналей, то все точки пересечения различны.

Замечу также (ни в коем случае не претендуя на откровение), что два случая (прямые $AB$ и $C_1D_1$ пересекаются либо параллельны), рассматриваемые большинством участников, с проективной точки зрения являют собой один случай.

Награды

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

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

[VAL]

Еще пара решений ММ217:

[VAL]

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

[VAL]

===========ММ218===============

ММ218 (5 баллов)

Найти наименьшее возможное количество диагоналей многогранника, имеющего 2017 ребер.

Решение

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

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

ММ218
Найти наименьшее возможное количество диагоналей многогранника, имеющего 2017 ребер.

Ответ: 1004 диагоналей.
______


Пример на 1004 построить легко (см. рисунок). Поставили треугольную призму "домиком" и с одной стороны -- со стороны $AB$ -- добавили 1004 точки в плоскости $ABDF$ (на рисунке отмечена только часть этих точек). Получили 1008 точек основания и 2 точки "сверху".
Количество рёбер: $1008+1004+4+1=2017$;
Количество (пространственных) диагоналей: 1004 -- все новые точки соединены с т.$E$. Других диагоналей нет.

Аргументы в пользу того, что меньше быть не может.
При рассмотрении суммарно всех диагоналей (пространственные + диагонали граней) нетрудно заметить, что наиболее выгодная стратегия лежит не в уменьшении числа вершин и не в разделении вершин по разным граням, а в максимальной консолидации вершин в одной грани-плоскости (поскольку $\binom{n}{2}$ растёт квадратично, при таком количестве точек это перевешивает остальные стратегии).
Поднять только одну вершину над плоскостью недостаточно -- количество рёбер будет чётным.
Поднять 2 вершины над плоскостью можно несколькими принципиально разными способами, которые несложно перебрать руками и убедиться, что представленный вариант принадлежит множеству самых выгодных.

Кроме того, приведу и свое решение задачи.

(Авторское решение)

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

Пусть многогранник имеет $v$ вершин, $e$ ребер и $f$ граней, а $h_1,h_2, \dots, h_f$ - количества сторон граней. Очевидно, что количество диагоналей такого многогранника многогранника вычисляется по формуле:

$$\begin{equation}d={v\choose2}-e-\sum_{i=1}^f\frac{h_i(h_i-3)}2\end{equation}$$

Легко видеть, что при фиксированных $e$ и $f$ сумма $\sum_{i=1}^f\frac{h_i(h_i-3)}2$ будет тем меньше, чем равномернее распределены значения $h_1$. И, соответственно, тем больше, чем больше самое большое из $h_i$ (в дальнейшем будем считать, что это $h_1$.
При четных $e$ $h_1$ может достигать $\frac e2$. Этот случай соответствует пирамидам, у которых $d=0$.

В нашем случае наибольшее значение $h_1=1008$ достигается при $v=1010, f=1009$. Соответствующие многогранники (еще две его грани четырехугольны, а остальные треугольны) легко строится. Их изображения можно найти в некоторых из приводимых решений. По формуле (1) (или в лоб) находим, что для такого многогранника $d=1004$.

Ясно, что с ростом $v$ уменьшаемое в (1) будет расти, а вычитаемое уменьшаться. Следовательно будет расти и $d$.

Картина, возникающая при уменьшении $v$, не столь очевидна. Ведь в этом случае в (1) будут уменьшаться и уменьшаемое и вычитаемое.
Так, при $v=1009, f=1010$ существует многогранник, имеющий одну 1007-угольную и 1009 треугольных граней. Впрочем, для того, чтобы понять, что у него больше диагоналей, чем вышеописанный, даже не нужно прибегать к формуле (1). Ведь, чтобы получить новый многогранник из предыдущего, достаточно малым шевелением:
а) перегнуть четырехугольные грани по диагонали (при этом добавятся две грани, два ребра и две диагонали);
б) спрямить одну из сторон 1008-угольного основания (при этом уйдут одна вершина, одна грань, два ребра и одна диагональ).
Итого, у нового многогранника получится $1004+2-1=1005$ диагоналей.

Но уже следующее уменьшение $v$ на 1 приведет к лавинообразному росту $d$. В самом деле, пусть $v=1008, f=1011$. Тогда наибольшее возможное значение $h_1$ равно 1004 (иначе просто некуда будет "впихнуть" необходимое количество граней и ребер). Остальные 1010 грани - треугольники ((см. соответствующий граф на рисунке). Для такого многогранника формула (1) дает $d=3009$.

При дальнейшем уменьшении $v$ наибольшее возможное $h_1$ убывает более быстрыми темпами и, следовательно, $d$ растет. Так, при наименьшем возможном $v$, равном 675, наибольшее $h_1$ будет 5, а $d={675\choose2}-2017-5=225453$.

Обсуждение

Подзаголовок "От двух до пяти", смутивший одних и вдохновивших других марафонцев, случайно достался этой задаче в наследство от ММ208.

Судя по присланным решениям, ММ218 оказалась достаточно сложной. Я же рассматривал ее, как весьма простую. По-видимому, это следствие того, что данную задачу я поставил уже после того, как исследовал вопросы о количестве диагоналей многогранников с фиксированным количеством вершин (граней). В частности, к этому времени я уже знал (и умел доказывать), что для минимизации количества диагоналей надо максимизировать число сторон самой большой грани.
Чтобы понять, насколько по-разному воспринимали сложность задачи участники и ведущий достаточно сравнить авторское решение с решением Владислава Франка, в котором Влад долго и скрупулезно обосновывает... неверный ответ Сразу отмечу (а то, ведь, не каждый осилит несколько страниц), что в решении Влада есть и верный ответ, но Влад предпочел сохранить в итоговом варианте весь тернистый путь к нему.

Изначально я планировал давать 5 баллов за решения, в которых будут указаны многогранники с 1004 и 1005 диагоналями и приведены (возможно, не идеально строгие, но убедительные) соображения, подтверждающие невозможность меньшего числа диагоналей. Т. е. близкие к тому, что приведено мной. Но в процессе изучения решений участников, я слегка персмотрел эти критерии в сторону увеличения призовых баллов. Я старался не замечать откровения типа $553+553=1006$ По крайней мере, при оценивании.

Разумеется, число 2017 не особенное по отношению к ММ218. Важна лишь его нечетность. Мне понравилось, что формула $d=\frac{e-9}2$ возвращает наименьшее возможное количество диагоналей многогранника с нечетным числом ребер для всех без исключения допустимых значений $e$ и дает заведомо бессмысленные значения для тех $e$, для которых не существует многогранников. Многие другие формулы, связанные с количеством диагоналей многогранников, допускают исключения для малых значений параметров.

Награды

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

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

[grizzly]

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

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

Интересно, что стоимостная оценка задачи влияет каким-то образом на её эстетическую оценку. Когда я пытался оценить эстетику, я задумался над этим. Скажем, при оценке сложности в 4 балла я бы счёл, что техника полного решения со строгим доказательством неадекватна оценке сложности и поставил бы эстетическую оценку 3. (Правда, в этом случае всё равно сохраняется риск, что я просто не вижу более простой по технике аргументации.) А вот если бы оценка сложности была 7, тогда я поставил бы 5 за эстетику. Поразмыслив, поставил 4.

[grizzly]

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

в которых будут указаны многогранники с 1004 и 1055 диагоналями ... Я старался не замечать откровения типа $553+553=1006$

Тьфу, понял наконец -- заменять нули пятёрками заразно :)

[VAL]

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

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

в которых будут указаны многогранники с 1004 и 1055 диагоналями ... Я старался не замечать откровения типа $553+553=1006$

Тьфу, понял наконец -- заменять нули пятёрками заразно :)

Вот-вот! Потому-то я и не имею морального права снимать баллы за такие вещи!

[VAL]

Срок приема решений ММ219 продлен до 22:00 29.11.16 (время московское)

[VAL]

===========ММ219===============

ММ219 (8 баллов)

Какое наибольшее количество диагоналей может иметь одиннадцатигранник?

Решение

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

Обсуждение

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

Интересно, что Олег Полубасов и Анатолий Казмерчук, обобщая задачу, передоказали теорему Грюнбаума-Моцкина
В упоминавшейся ранее книжке Бранко Грюнбаума есть расширенный вариант этой теоремы.

Пусть $(g_3, g_4, g_5, g_6)$ - вектор, характеризующий количества треугольных, четытеругольных, пятиугольных и шестиугольных граней простого (степень каждой вершины равна 3) многогранника, и других граней у него нет, т.е. по теореме Эберхарда $3g_3+2g_4+g_5=12$. Тогда:
векторы $(0, 0, 12, g_6)$ и $(0, 6, 0, g_6)$ реализуемы тогда и только тогда, когда $g_6\ne 1$;
вектор $(4, 0, 0, g_6)$ реализуем тогда и только тогда, когда $g_6$ четно и отлично от 2;
вектор $(3, 1, 1, g_6)$ реализуем тогда и только тогда, тогда $g_6$ нечетно и больше 1.

Предлагая данную задачу, я уже знал ответ на вопрос о наибольшем возможном числе диагоналей многогранника с произвольным фиксированным количеством граней. Но, в отличие от Анатолия и Олега я не предоказывал теорему Грюнбаума-Моцкина, а нашел ее в сети.
Вот как выглядит центральный фрагмент авторского решения MM219 "методом чайника" в свете этой теоремы:

Предположим, что существует многогранник с вектором граней $(0, 1, 10, 0)$. Фрагмент соответствующего графа приведен в левой части рис. 1.



Отсечением от него ребра, ровно одна вершина которого принадлежит четырехугольной грани, получим многогранник с вектором $(0,1,10,1)$. У полученного многогранника отсечем шестигранник, как показано в правой части рис 1. Получим многогранник с вектором граней $(0,0,12,1).$ Но по теореме Грюнбаума-Моцкина такого многогранника не существует. Значит, не существует и исходного многогранника. Остается привести пример многогранника с вектором $(0,2,8,1)$, имеющего 73 диагонали.

Награды

За решение и обобщение ММ219 Олег Полубасов и Анатолий Казмерчук получают по 12 призовых баллов.
За решение ММ219 участникам начислены следующие призовые баллы:
Владислав Франк - 8;
Владимир Чубанов и Виктор Филимоненков- по 6.

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