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

[VAL]

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

На рисунке 5.г) у Олега Полубасова получилось меньше, чем $2\sqrt 2$

Это в пределе. При соответствующем подходе к его вычислению

[Masik]

А мне кажется, что схема разрезаний, предложенная Сергеем Половинкиным, заслуживает большего интереса. По крайней мере, авторские разрезания на 9, 10 и 11 частей придерживаются этой схемы. Моё разрезание на 6 частей углубляет эту схему ещё на один уровень (что заставляет задуматься). Закономерно возникает вопрос: нельзя ли получить минимальные решения, придерживаясь исключительно этой схемы разрезания? Тогда число рассматриваемых вариантов становится смехотворно малым.
В общем, верните Сергею Половинкину честно заработанный балл за верный ответ и за "расшатывание" задачи.
Олег Полубасов.

[VAL]

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

А мне кажется, что схема разрезаний, предложенная Сергеем Половинкиным, заслуживает большего интереса. По крайней мере, авторские разрезания на 9, 10 и 11 частей придерживаются этой схемы.

То, что для 5 частей такой подход заведомо не оптимален (если я верно понял, о какой схеме идет речь), очевидно. Что же касается ее касается ее перспективности для общего случая, то... общий случай Сергей не рассматривал.

Цитата:

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

Мне тоже кажется, что с ростом $n$ должен возникать какой-то общий принцип.

[Masik]

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

То, что для 5 частей такой подход заведомо не оптимален (если я верно понял, о какой схеме идет речь), очевидно.

Нет, Владимир, видимо, Вы не верно поняли. Рисунок 5а в моём решении иллюстрирует именно этот подход, и для остальных разбиений меньше чем на 12 частей решения с помощью такого подхода рассмотрены решающими или ведущим и являются минимальными из найденных. Это, конечно, ничего не доказывает для общего случая, но как раз и возбуждает желание доказать, как-то ещё покрутить в уме эту задачу.

[Masik]

Вероятно, можно доказать следующую гипотезу. Если имеется некоторое разрезание, то его можно заменить топологически эквивалентным разрезанием, в котором суммарная длина отрезков будет такой же, но все разрезы – прямые, без изломов. В тексте Анатолия Казмерчука утверждается что-то подобное, но без доказательства.
Теперь рассмотрим иерархические схемы прямолинейных разрезаний. Первый разрез (горизонтальный) делит исходный квадрат на две (не обязательно равновеликие) фигуры. Каждый следующий разрез может быть как горизонтальным, так и вертикальным, и делит одну из фигур на две (не обязательно равновеликие).
Симметричная схема разрезания квадрата на 5 частей, в которой центральная фигура является квадратом, не является иерархической. Она гипнотизирует своей симметрией и отвлекает от более перспективных направлений исследования. Выскажу вторую гипотезу: минимальной суммарной длины отрезков при разрезании квадрата на любое число частей можно достичь с помощью иерархической схемы разрезания.
Предположим, что обе гипотезы удалось доказать. Чего мы этим достигли? Исходная задача, имеющая бесконечное пространство решений, превратилась в комбинаторную. И хотя число возможных иерархических разрезаний экспоненциально зависит от числа частей, нет никакой необходимости перебирать их все. Проанализировав опубликованные рисунки, я записал некоторые из оптимальных разрезаний на число частей от 2 до 11 в следующем виде.

2 = 1 + 1.
3 = 2 + 1.
4 = 1 + 2 + 1.
5 = 1 + 3 + 1 = (1 + 2 + 1) + 1.
6 = 1 + (1 + 2 + 1) + 1.
7 = 2 + 3 + 2.
8 = 2 + 4 + 2 = (1 + 2 + 1) + (1 + 2 + 1) = 1 + (1 + 2 + 2 + 1) + 1 = 1 + (1 + (1 + 1) + (1 + 1) + 1) + 1.
9 = 1 + 2 + 3 + 2 + 1.
10 = 1 + 2 + 4 + 2 + 1.
11 = 1 + 2 + 5 + 2 + 1.

Объяснять принцип записи, полагаю, не требуется, SAPIENTI SAT.
Предлагаю включить в один из следующих туров какое-нибудь развитие этой задачи, ведь задача явно не доисследована. Задачи комбинаторной геометрии традиционно трудны. Вот, например, в задаче ММ200 Анатолий Казмерчук нашёл очень красивое симметричное решение. А последовательность T(m) мы так до сих пор и не знаем.

[VAL]

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

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

На мой взгляд, доказательство (ну ладно, основная идея) у Анатолия есть.

Цитата:

Теперь рассмотрим иерархические схемы прямолинейных разрезаний. Первый разрез (горизонтальный) делит исходный квадрат на две (не обязательно равновеликие) фигуры. Каждый следующий разрез может быть как горизонтальным, так и вертикальным, и делит одну из фигур на две (не обязательно равновеликие).
Симметричная схема разрезания квадрата на 5 частей, в которой центральная фигура является квадратом, не является иерархической. Она гипнотизирует своей симметрией и отвлекает от более перспективных направлений исследования. Выскажу вторую гипотезу: минимальной суммарной длины отрезков при разрезании квадрата на любое число частей можно достичь с помощью иерархической схемы разрезания.
Предположим, что обе гипотезы удалось доказать. Чего мы этим достигли? Исходная задача, имеющая бесконечное пространство решений, превратилась в комбинаторную. И хотя число возможных иерархических разрезаний экспоненциально зависит от числа частей, нет никакой необходимости перебирать их все. Проанализировав опубликованные рисунки, я записал некоторые из оптимальных разрезаний на число частей от 2 до 11 в следующем виде.

2 = 1 + 1.
3 = 2 + 1.
4 = 1 + 2 + 1.
5 = 1 + 3 + 1 = (1 + 2 + 1) + 1.
6 = 1 + (1 + 2 + 1) + 1.
7 = 2 + 3 + 2.
8 = 2 + 4 + 2 = (1 + 2 + 1) + (1 + 2 + 1) = 1 + (1 + 2 + 2 + 1) + 1 = 1 + (1 + (1 + 1) + (1 + 1) + 1) + 1.
9 = 1 + 2 + 3 + 2 + 1.
10 = 1 + 2 + 4 + 2 + 1.
11 = 1 + 2 + 5 + 2 + 1.

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

Цитата:

Предлагаю включить в один из следующих туров какое-нибудь развитие этой задачи, ведь задача явно не доисследована.

Таких задач в марафоне...

Цитата:

Задачи комбинаторной геометрии традиционно трудны. Вот, например, в задаче ММ200 Анатолий Казмерчук нашёл очень красивое симметричное решение. А последовательность T(m) мы так до сих пор и не знаем.

Более того. Зная $T(12)$, мы знаем точных значений $T(m)$ для нескольких меньших $m$.

[VAL]

Ответил на уточняющий вопрос по условию ММ205 в личной переписке.
Продублирую ответ здесь.
В условии ММ205 речь идет о натуральных числах, имеющих в точности 2016 натуральных делителей. А не о числах, имеющих не менее 2016 делителей.

[VAL]

===========ММ204===============

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

Найти натуральное число, которое в трех различных системах счисления записывается 102, 201 и 20001 соответственно.

Решение

Привожу решения Олега Полубасова, Ариадны и Игоря Ханова.

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

ММ204
Пусть основания этих систем равны соответственно $ a, b, c $. Имеем $ a^2+2=2b^2+1=2c^4+1 $, откуда сразу $ b=c^2 $ и остается уравнение $ a^2+2=2c^4+1 $. Видим, что $ a $ - нечетное, поэтому вводим замену $ a=2t+1 $. Получаем $ 2c^4=a^2+1=(2t+1)^2+1=4t^2+4t+2 $ и $ c^4=2t^2+2t+1=t^2+(t+1)^2 $. Воспользуемся формулами пифагоровых троек: $ t=u^2-v^2, t+1=2uv, c^2=u^2+v^2 $. Тогда $ (u, v, c) $ - тоже пифагорова тройка и мы можем положить $ u=12, v=5, c=13 $. Действительно, в таком случае $ t=12^2-5^2=119, t+1=2\cdot 12\cdot 5=120 $. Тогда $ a=2t+1=2\cdot 119+1=239, b=13^2=169 $ и искомое число равно $ 2\cdot 13^4+1=57123 $.
Ответ: 57123.

Обсуждение

Задача ММ204 оказалась проходной. Она не вызвала каких-то затруднений участников, но и не особо им понравилась.
Я тоже не буду многословен при обсуждении. Скажу только, что я заранее решил, что не буду оценивать наличие (отсутствие) обоснования единственности решения, поскольку это, скорее, вопрос эрудиции.

Награды

За решение задачи ММ204 Полубасов, Евгений Гужавин, Сергей Половинкин, Игорь Ханов, Виктор Филимоненков, Анатолий Казмерчук, Валентина Колыбасова (Ариадна), Алексей Извалов и worm2 получают по 5 призовых баллов.

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

[VAL]

===========ММ205===============

ММ205 (7 баллов)

Вася выписывает в порядке возрастания натуральные числа, имеющие по 2016 натуральных делителей. На каком шаге он впервые выпишет число, не кратное 2016?

Решение

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

Обсуждение

Задача ММ205, оказалась непростой для участников. Я получил всего 5 решений. Альтернативное объяснение, что задача просто не понравилась марафонцам, плохо согласуется с высоким уровнем оценок, выставленных теми, кто, все же, откликнулся.

Любопытно, что до получения последнего (пятого) решения, ответы ни разу не повторились.
При этом все полученные решения были, по сути, верными.
Просто Сергей Половинкин сосчитал одно и то же число два раза.
Виктор Филимоненков, наоборот потерял одно число. Изначально увидев, ответ на единицу меньший, чем у меня, я был почти уверен, потерян единственный случай с множителем $3^6$. Но нет, Виктор ограничился рассмотрением простых множителей, не превышающих 41, упустив один случай с множителем 43.
Наконец, Владимир Дорофеев вообще не добрался до ответа. Он нашел наименьшее число, не кратное 2016 и имеющее 2016 делителей, три возможных канонических разложения чисел, подлежащих перебору и описал возможный алгоритм перебора. Но реализовывать этот алгоритм не стал.

Вопросы, смежные поставленному в ММ205 рассмотрел только Олег Полубасов (см. его решение).
От себя добавлю что в OEIS не было не только последовательности натуральных чисел свободных от квадратов, пополненной числом 4, но и еще, как минимум, двух последовательностей, естественным образом связанных с ММ205. А именно:
последовательности натуральных чисел $d$, таких что наименьшее натуральное число, имеющее ровно $d$ делителей, кратно $d$;
подпоследовательности A005179, состоящей из чисел, кратных соответствующим $n$.
На сегодняшний день они добавлены и имеют статус черновиков. Это A262981 и A262983.

Награды

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

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

[VAL]

===========ММ206===============

ММ206 (11 баллов)

Задача ММ206 является прямым продолжением задачи ММ77

Каждое из $n$ натуральных чисел, идущих подряд, имеет ровно $k$ натуральных делителей. Какое наибольшее значение может принимать n, если
1) $k = 18$;
2) $k = 20$;
3) $k = 22$;
4) $k = 202$.

Замечание: Относительно скромное количество призовых баллов за эту задачу обусловлено тем, что при ее решении можно воспользоваться не только решением ММ77, но и результатами статьи, на которую есть ссылка в обсуждении.

Решение

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

Обсуждение

Хотя Марафон не подвергался никаким санкциям, в середине 21-го тура он оказался в глубоком кризисе
Но ли я перестарался, то ли участники недостарались... Так или иначе, я получил всего два решения задачи ММ206.
Не исключаю, что кому-то просто не хватило времени. Конечно, времени было достаточно: задача была опубликована еще в мае, да и от разбора ММ205 ее отделяют 2 недели (а не традиционная неделя). Но, полагаю, многие участники по студенческой привычке приступают к решению исключительно в последний день.

Следующая задача (ММ207) является естественным продолжением ММ206. Само собой, этот факт наводит на мысль, не постигнет ее участь разбираемой задачи. Надеюсь, разбор ММ206 поможет участникам справиться с ММ207.

Теперь по сути задачи.
Обозначим через $M(k)$ наибольшее возможное количество последовательных натуральных чисел, имеющих в точности $k$ делителей. Ясно, что для каждого конкретного $k$ $M(k)$ имеет конечное значение. В то же время, согласно гипотезе Эрдёша, для каждого натурального числа $m$, найдется $k$ такое, что $M(k) \ge m$.

Очевидно, что $M(k)=1$ для нечетных $k$.

Мне удалось найти точные значения $M(k)$ для 55 конкретных четных значений $k$ (ранее $M(k)$ было известно только для $k \in \{2,4,6,8,10,14,16\}$). Конкретные $k$ и числа, с которых начинаются соответствующие последовательности, см. здесь.

Я практически уверен, что, если $k$ - удвоенное простое, большее 3, то $M(k)=3$ (пункты 3 и 4 - частные случаи этого утверждения).
Еще одна правдоподобная гипотеза: если $k$ кратно 4, но не кратно 3 (пункт 2), то $M(k)=7$.
Высказанные предположения стали бы теоремами, если бы была доказана гипотеза Бейтмана-Хорна или какой-либо из ее более слабых вариантов, например, гипотеза Шинцеля H или гипотеза Диксона.

Сложнее обстоит дело четными $k$, не кратными 4.

Если при этом $k$ кратно 3, то можно получить оценку $M(k) \le 7$. Однако, точное значение $M(k)$ известно только для двух конкретных значений $k$. Причем для этих $k$ наибольшее возможное количество последовательных чисел, имеющих по $k$ делителей, равно не 7, а 5 (пункт 1 и пункт 4 задачи ММ77).

Если $k=2m$, где $m$ - составное, не кратное 3, то справедлива оценка $M(k) \le 5$. Однако я не знаю ни одного примера, для которого эта граница достигается. Более того, я не уверен в существовании таких примеров.

Мне удалось найти 13, а затем и 14 последовательных чисел, имеющих по 24 делителя.
Некоторые подробности этого поиска можно найти в авторском решении MM206

Награды

За решение задачи ММ206 Анатолий Казмерчук получает 12 призовых баллов, а Василий Дзюбенко - 7 призовых баллов.

Эстетическая оценка задачи - 5 баллов
(То есть, оценившему ее Анатолию Казмерчуку задача понравилась )

[VAL]

===========ММ207===============

ММ207 (13 баллов)

Обозначим через $A(a,d)$ максимально возможное количество последовательных натуральных чисел таких, что первое из имеет ровно $a$ натуральных делителей, второе - $a+d$, третье - $a+2d$ и т.д. (иными словами, количества делителей последовательных чисел образуют арифметическую прогрессию с первым членом a и разностью $d$).
1) найти наибольшее возможное значение $A(n,1)$;
2) найти наибольшее возможное значение $A(n,3)$;
3) найти $A(2,2)$;
4) найти $A(4,2)$;
5) доказать, что при подходящем n $A(n,2) \ge 8$.

Решение

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

Вложение:

Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_207.docx [54.12 Кб]
Скачиваний: 497

Вложение:

Комментарий к файлу: Решение Василия Дзюбенко
mm_207_Dzubenko.docx [21.7 Кб]
Скачиваний: 482

Вложение:

Комментарий к файлу: Решение Олега Полубасова
MM207_Полубасов.pdf [401.46 Кб]
Скачиваний: 496

Обсуждение

Как я и ожидал, после реакции участников на ММ206 близко родственная ММ207 не вызвала бурного потока откликов.
Но некоторый прогресс, все же наблюдается. А в процентном отношении рост очень даже неплохой!

Анатолий Казмерчук прислал мне табличку содержащую точные значения (для одних случаев) и оценки (для других) $A(a,d)$ для всех $a$ и $d$, не превосходящих 8. По мнению самого Анатолия эта таблица пока весьма "сырая". Поэтому по его же просьбе я не привожу эту таблицу. По этой же причине ("сырости" таблицы, а не просьбе автора) дополнительные призовые баллы за решение Анатолия достаточно скромны. Я планирую после аккуратной проверки опубликовать эту таблицу и надеюсь, что это "после" когда-нибудь настанет.

Некоторые повторы в решении Василия Дзюбенко вызваны тем, что я механически объединил два файла, присланных мне Василием.

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

В заключение приведу пример, показывающий, что $A(4,4) \ge 10$. Десять последовательных чисел, начиная с $n=41295713132636191453967523681640615$ имеют соответственно 4, 8, 12, 16, 20, 24, 28, 32, 36 и 40 делителей.

Награды

За решение задачи ММ207 Олег Полубасов и Анатолий Казмерчук получают по 15 призовых баллов, а Василий Дзюбенко - 13 призовых баллов.

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

[VAL]

Срок приема решений задачи ММ208 продлен на одни сутки.

[Masik]

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

[VAL]

===========ММ208===============

ММ208 (7 баллов)

От двух до пяти.

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

Решение

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

Вложение:

Комментарий к файлу: Решение Василия Дзюбенко
MM208_Dzubenko.docx [15.61 Кб]
Скачиваний: 482

Вложение:

Комментарий к файлу: Решение Олега Полубасова
MM208_Полубасов.pdf [212.47 Кб]
Скачиваний: 501

Вложение:

Комментарий к файлу: Решение Анатолия Казмерчука
Kazmerchuk_pr_208.docx [90.56 Кб]
Скачиваний: 472

Обсуждение

Участники Марафона, сошедшие с дистанции на отметке ММ206, потихоньку возвращаются. На ММ208 получено 5 откликов. Маловато, конечно. Но, все же не 2, как на ММ206. Тем самым на данном участке дистанции был реализован девиз данной задачи - "От двух до пяти".

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

ММ208 допускает очевидные обобщения и аналоги по всем параметрам задачи: количество слагаемых; число представлений; максимальное число слагаемых для которых нет взаимной простоты.
Мне представляется интересным аналоги и обобщение именно по последнему параметру. Но участники ограничились первыми двумя.

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

$$ \begin{array}{l}44889 =\\ 5642 + 6783 + 9614 + 10695 + 12155 =\\ 5434 + 7735 + 8835 + 9982 + 12903 =\\ 4641 + 7315 + 8602 + 10005 + 14326 =\\ 5187 + 6545 + 8294 + 10005 + 14858 \end{array}$$

Первые два представления соответствуют набору (2), вторые два - набору (1).

Существуют три числа, меньшие 44813, допускающие представления в виде сумм, отвечающим разным наборам. Это числа 43467, 43723, 43913. У каждого из них имеется по одному представлению в виде суммы пяти слагаемых, отвечающему каждому из наборов (1) и (2).

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

Награды

За решение задачи ММ208 Олег Полубасов, Анатолий Казмерчук и Сергей Половинкин получают по 8 призовых баллов, а Василий Дзюбенко - 5 призовых баллов.

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

[fiviol]

Было приятно обнаружить, прочитав условие ММ208, что уважаемый ведущий марафона решил занять нас гитикообразными конструкциями, которые я так люблю. :) Можно было бы сформулировать задачу примерно так:
найти минимальное число, четырьмя разными способами представимое в виде:
НОЕТ+АКЫН+РЕКИ+ГОРЫ+ГАТИ
(одинаковым буквам соответствуют одинаковые простые числа, разным - разные, знаки умножения между переменными, как положено , отсутствуют).

Увы, объявленная в начале тура ориентированность задач на использование компьютера заставила меня в этот раз сойти с дистанции - задачу я не решил. :(