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

[worm2]

Хотел бы высказаться по поводу задачи ММ187 из XIX тура.
Отличная задача! Автор знает толк в троллинге

[nnosipov]

worm2 в сообщении #769250 писал(а):

Хотел бы высказаться по поводу задачи ММ187 из XIX тура.
Отличная задача! Автор знает толк в троллинге

Да, она мне тоже бросилась в глаза. Конечно, это хорошо известный сюжет, который лично я представил бы в таком виде: докажите, что если $a$, $b$, $c$ --- натуральные числа и

$$ \frac{a^2+b^2}{ab+1}=c, $$

то $\gcd{(a,b)}=\sqrt{c}$. Последний пункт (где число $2013$) смотрится несколько странно: есть совершенно банальная причина, по которой указанное равенство невозможно. Впрочем, это могло быть и запланировано автором.

[VAL]

nnosipov в сообщении #769256 писал(а):

Конечно, это хорошо известный сюжет, который лично я представил бы в таком виде: докажите, что если $a$, $b$, $c$ --- натуральные числа и

$$ \frac{a^2+b^2}{ab+1}=c, $$

то $\gcd{(a,b)}=\sqrt{c}$. Последний пункт (где число $2013$) смотрится несколько странно: есть совершенно банальная причина, по которой указанное равенство невозможно. Впрочем, это могло быть и запланировано автором.

Во-первых, запланировано.
А во-вторых...
Я всегда приветствую обсуждение марафонских задач.
Но до публикации разбора желательно делать это в ЛС.

-- 30 сен 2013, 08:47 --

worm2 в сообщении #769250 писал(а):

Хотел бы высказаться по поводу задачи ММ187 из XIX тура.
Отличная задача! Автор знает толк в троллинге

См. "во-вторых" из моего ответа nnosipov'у.

[VAL]

Я был бы не я, если ни разу не переврал в условиях задач.
Но я - это я.
Поэтому первый пункт в условии ММ182 следует понимать так:
1) в каноническом разложении n имеется более двух простых делителей;

[VAL]

В связи с пожеланиями некоторых конкурсантов прием решений ММ181 продлен на сутки.

[VAL]

========= ММ181 ==========

Разминка

ММ181 (3 балла)

Существует ли натуральное число n, среди остатков от деления которого на все натуральные числа меньшие n чаще всего встречается остаток 2013?

Решение

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

Обсуждение

Числа $n$ с рекордным (бОльшим, чем у всех меньших чисел) значением $\tau(n)$ называются highly composite numbers (вслед за Андреем Халявиным я буду называть их "граничными"). Эти числа упомянуты как в строгих, так и в приблизительных обоснованиях обобщения ММ181. Они, конечно же, есть в OEIS (A002182).
Числа, которые Андрей Халявин в своем решении обозначил через $G_n$, также есть в OEIS (A086332). Правда, их было приведено всего 16 штук. При подготовке данного разбора я добавил в OEIS список, содержащий первые 38 чисел $G_n$.
Утверждение Андрея о том, числа $G_n$ не обязаны существовать для всех $n$, скорее всего, является перестраховочным. Исследование первой тысячи граничных чисел показывает, что $G_n$ встречаются среди них относительно редко. В среднем на каждые 27 граничных чисел встречается одно $G_n$ и интервал между $G_n$ имеет тенденцию к возрастанию.

А вот последовательности A230399 в OEIS не было. Но в связи с обобщением ММ181 она появилась.

Как водится я испытывал трудности при присуждении призовых баллов.
Ясно, что те конкурсанты, которые только нашли подходящие числа, но не сделали попыток обобщения, получили номинал. Столько же баллов получили те, кто обобщил задачу, даже привел (не слишком строгие) обоснования бесконечности требуемых чисел для любого данного остатка, но при этом не нашел ни одного подходящего числа даже для 2013
На один балл выше номинала оценено решение, где найдены подходящие числа и сделаны (но не отягощены доказательствами) обобщения.
Наиболее сложной для меня задачей было оценить решения Олега и Андрея. С одной стороны, у Андрея охвачен более общий случай, а у Олега доказана только бесконечность множества чисел, для которых именно 2013 является наиболее часто повторяющимся остатком. Но:
Во-первых, решение Олега легко обобщается с $k = 2013$ на любое $k$.
А во-вторых, решение Андрея представляется мне неоправданно тяжеловесным.
Учитывая вышесказанное, я несколько раз менял призовые баллы Андрея и Олега. Текущая версия представлена в разделе "награды"

Приведу набросок своего доказательства общего утверждения: для любого целого неотрицательного $k$ найдется бесконечно много натуральных чисел $n$, при делении которых на все натуральные числа, меньшие $n$, остаток $k$ встречается наиболее часто.
Почему только набросок? Жаждущие деталей могут заглянуть в решение Олега (в идейном плане оно близко моему), а особо жаждущие могут попытаться осилить решение Андрея (оно тоже основано на тех же идеях)
Мой же опус предназначен для тех, кому лень углубляться в детали, но хочется понять суть.

Не теряя общности, можно считать, что $k$ достаточно велико. Например, больше 100.
Возьмем большое граничное число $b$, например, имеющее не менее $k$ различных простых сомножителей.
Ясно, что в каноническом разложении $b$ встречаются все первые $k$ простых чисел, причем показатели идут в порядке невозрастания.
Пусть $c$ - ближайшее к $b$ (неважно с какой стороны) число, имеющее не менее чем $\tau(b)-k$ делителей.
Тогда несколько первых простых делителей $b$, произведение которых больше $k$, обязаны входить и в разложение $c$. (Если это не так, заменим в $c$ какие-то из больших делителей на отсутствующие и, увеличив показатели степени у маленьких делителей, получим число меньшее $b$, но имеющее больше делителей, что противоречит выбору $b$.)
Но тогда НОД $b$ и $c$ больше $k$, то есть $c$ отстоит от $b$ более чем на $k$ и, значит $b+k$ - искомое число.

Замечу, что на практике не обязательно стартовать исключительно с граничных чисел. В качестве $b$, как правило, годятся любые большие числа, насыщенные мелкими делителями.

В заключение сформулирую еще один вопрос (ответ на который, я лично искать не собираюсь
У числа 525 нет одного явного лидера среди остатков от деления на числа от 1 до 525 (я чуть-чуть изменил исходное условие, но это не важно). Каждое из чисел 0, 5, 21 встречается среди остатков по 12 раз.
Возникает вопрос: для любого ли конечного множества остатков найдется число, для которого данные остатки будут встречаться чаще других и одинаковое число раз? Такая вот "Монгольская теорема об остатках"

Награды

За решение и обобщение ММ181 Андрей Халявин получает 8 призовых баллов, Олег Полубасов - 7 призовых баллов, Сергей Половинкин - 4 призовых балла, а Виктор Филимоненков, Антон Никонов, Алексей Волошин, Николай Дерюгин, Евгений Гужавин и Дмитрий Пашуткин - по 3 призовых балла.

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

[VAL]

========= ММ182 ==========

Продолжаем разминаться

ММ182 (3 балла)

Назовем натуральное число n суперделимым, если:
1) в каноническом разложении n имеется более двух простых делителей;
2) для любого собственного подмножества множества простых делителей n число n кратно сумме элементов этого подмножества.
Доказать, что существует бесконечно много суперделимых чисел.

Решение

Привожу решение Олега Полубасова.

Обсуждение

Конечно, прийти к тому, что суперделиммыми будут все натуральные числа вида $2^a3^b5^c7^d$, где $a>2, b>1, c,d>0$ совсем не трудно.
Сама эта легкость казалась мне достаточным намеком на то, я жду не только решения, но и обобщений ММ182. Тем не менее, обобщать взялись далеко не все. Что ж, это законное право конкурсантов. А законное право ведущего, поощрять тех, кто не только решил, но и обобщил задачу

Замечу, то, что в предыдущем абзаце именовалось "обобщениями" по сути означает отсутствие обобщений. А именно:
Указанная серия суперделимых чисел - единственная. После нескольких попыток построить другие серии невозможность такого построения становится очевидной. Но доказательство не столь очевидно, как само утверждение.
Не удается отбросить и характеристику "собственное" (точнее, "нетривиальное", как справедливо указали мне несколько конкурсантов) во втором пункте условия.

Награды

За решение и обобщение ММ182 Олег Полубасов получает 6 призовых баллов, Сергей Половинкин - 5 призовых баллов. За решение задачи ММ181 Андрей Халявин, Виктор Филимоненков, Евгений Гужавин, Анатолий Казмерчук, Николай Дерюгин, и Дмитрий Пашуткин получают по 3 призовых балла.

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

[Masik]

Политика ведущего, надеюсь, всем уже понятна. В отличие от предыдущего тура, в этом туре задачи изначально оценены довольно низко. То есть, ведущий настроился за правильное решение задачи давать номинал, а основные баллы - за обобщение(я). Желаю всем удачных обобщений! Лично я на попытках обобщения ММ183 сильно обломался.

[VAL]

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

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

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

Цитата:

Лично я на попытках обобщения ММ183 сильно обломался.

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

[VAL]

Под воздействием справедливой критики переформулировал условие ММ188. Надеюсь, получилось более внятно.

[VAL]

Многочисленные (ведь больше одного - это много!) просьбы участников о продлении срока приема решений ММ183 счастливо совпали с моим собственным цейтнотом.
Поэтому прием решений будет продолжен, по крайней мере, до 2.11.13

[VAL]

========= ММ183 ==========

Легкая задача с очевидным неочевидным обобщением

ММ183 (3 балла)

Про пять чисел $a,b,c,d,e$ известно, что $a<b<c<d<e$. Попарные суммы этих чисел выписали в порядке неубывания. Найти число вариантов расположения сумм в этом списке в зависимости от конкретных значений исходных чисел.


Решение

Привожу решения на любой вкус:
Андрея Халявина (кратко, обоснованно, но без обобщений);
Олега Полубасова (решение и модификации);
Анатолия Казмерчука (модификация без решения)

Обсуждение

Остановимся на обобщении ММ183 и ее близких аналогов.
Хотя Олег Полубасов и утверждает, что ему неизвестно, какие обобщения имел в виду ведущий. полагаю он немного лукавит, поскольку под номером 1 в его списке стоит "правильная" версия.
Тем более, что остальные "обобщения" Олега - это не обобщения а вариации на тему (что, разумеется, тоже приветствуется).
Меня же в первую очередь заинтересовал вопрос о наличии общей формулы, наподобие той, что есть для последовательности A003121 в OEIS.
Эта последовательность вообще сыграла злую шутку с некоторыми участниками. Значения $a(2), a(3), a(4), a(5)$ совпадают с ответами на аналоги ММ183 при соответствующих значениях $n$. А среди многочисленных интерпретаций есть и такая: количество способов заполнения треугольной таблицы числами $1,2,\dots,{n\choose2}$, так чтобы в каждой строке и в каждом столбце числа возрастали.
А количество наших сумм - тоже треугольное число. Более того, решетка (ч.у.м., в котором у любой пары элементов есть точная верхняя и точная нижняя грань) имеет именно треугольный вид.
(На рисунке представлена решетка сумм для восьми чисел. В примерах рассматривается случай шести чисел, но картинку я рисовал раньше, когда оптимистично замахивался на любые $n$):



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

$$\begin{tabular}{c|cccc} b &1\\ c &2 &4\\ d &3 &6 &8\\ e &5 &7 &9 &10\\ \hline &a &b &c &d\\ \end{tabular}$$

Выпишем попарные суммы элементов $a<b<c<d<e$ в следующем порядке: на $i$-е место поставим сумму индексов столбца и строки, на пересечении которых стоит число $i$.
Для нашего треугольника получим $a+b, a+c, a+d, b+c, a+e, b+d, b+e, c+d, c+e, d+e$.
Легко убедиться, что при $n\le5$ указанное соответствие задает биекцию, между всеми треугольниками и всеми вариантами упорядочивания сумм.

К моменту, когда мне прислали первое решение с выходом на A003121, я уже давно имел ответ о числе упорядочиваний сумм для $n=6$ и не сомневался в нем.
Этот ответ был 168. А шестой член A003121 равен 286. Поэтому я решил, что совпадение начальных членов A003121 и ответов к ММ183 для малых $n$ - случайность. И успокоился. Но ненадолго. В тот же день пришло еще одно решение с ответом 286 для $n=6$.
Уверенность в правильности моего ответа пошатнулась и я кинулся перепроверять свое решение. И, как мне показалось, разгадал загадку.
Дело в том, что первоначально условие ММ183 выглядело немного по-другому. В нем говорилось, что все попарные суммы различны. Но при публикации я убрал эту оговорку, рассуждая примерно так:
для $n=5$ решение не изменится, зато ответ будет попроще, а обобщения... а обобщения все равно можно рассмотреть и в предположении попарного различия сумм и без него.
Ответ 168 соответствовал ситуации, когда все суммы различны. Ясно, что если допустить равенство сумм число упорядочиваний по неубыванию возрастет.
Например, при различии всех сумм порядок $a+d, a+e, b+c, b+d, a+f, b+e, b+f, c+d, c+e, c+f, d+e$ невозможен.
В самом деле, из неравенств $a+e<b+c$ и $b+d<a+f$ следует, что $d+e<c+f$.
Но такое упорядочивание легко достигается, если допустить равные суммы. Например, при $a=1,b=5,c=9,d=12,e=13,f=16$.
Итак, все ясно! Добавляем в OEIS новую последовательность, в описание A003121 добавляем новую интерпретацию и ссылку на новую последовательность.
Но на всякий случай я решил пересчитать возможные упорядочивания сумм, среди которых могут быть равные.
И их оказалось 244. Т.е. меньше, чем способов заполнить треугольник числами от 1 до 15.
Приведу пример "лишнего" треугольника:

$$\begin{tabular}{c|ccccc} b &1\\ c &2 &5\\ d &3 & 6& 10\\ e &4 &7 &11 &13\\ f &8 &9 &12 &14 &15\\ \hline &a &b &c &d &e\\ \end{tabular}$$

Описанный выше способ ставит ему в соответствие такое "упорядочивание" множества сумм:
$a+b,a+c,a+d,a+e,b+c,b+d,b+e,a+f,b+f,c+d,c+e,c+f,d+e,d+f,e+f$.
Но из $a+e\le b+c$ и $b+e\le a+f$ следует $2e\le c+f$. Но $c+f\le d+e<2e$ и мы пришли к противоречию.

Что ж? Тем лучше. Добавим в OEIS две новых последовательности!
А общая формула?.. Будем думать.

В прилагаемом файле приведены 286 расположений сумм, соответствующих 286 способам заполнения треугольника числами 1,2,..., 15. Они разбиты на три группы:
168 расположений соответствующих упорядочиваниям попарно различных сумм;
76 реализуемых только при наличии равных сумм;
42 нереализуемых.

И еще об одной сложной задаче. Эту задачу задал мне своей версией решения Анатолий Казмерчук. Задача - во сколько баллов оценить его решение?
Готов убедительно обосновать любое количество баллов от 0 до 7 включительно! Не верите?! Тогда обосную крайние случаи:

0. Исходная задача вообще не решена, решавшаяся вместо нее решена неверно - итого 0 баллов.
...
7. Исходная задача правильно решена в первом же пункте измененной задачи, гораздо более сложной, чем исходная. Измененная задача решена практически верно: правильно выбраны случаи; верно найдены ответы для каждого случая; верно найдены пересечения всех случаев. И лишь, собирая все верно найденное воедино, Анатолий допустил оплошность, за которую можно и не снижать баллы. Итак, можно считать, что решена и исходная и более сложная задача (в точности та, за которую начислены дополнительные баллы Олегу Полубасову). Значит, и оценка должна быть такой же!

В итоге я остановился на 5 баллах. А сколько поставили бы вы?


Награды

За правильное решение и обобщение ММ183 Олег Полубасов получает 7 призовых баллов, Сергей Половинкин - 5 призовых баллов, Антон Никонов - 4 призоых балла. За правильное решение задачи ММ183 Андрей Халявин, Виктор Филимоненков, и Дмитрий Пашуткин получают по 3 призовых балла. За верные наблюдения (не приведшие, однако, к правильному решению) Николай Дерюгин получает один призовой балл.
За практически правильное решение гораздо более сложного аналога ММ183 Анатолий Казмерчук получает 5 призовых баллов.

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

[kknop]

А почему A003121 не взято в тег "oeis", он же специально для таких случаев существует? Ведь со ссылкой намного красивее: A003121

[VAL]

kknop в сообщении #783916 писал(а):

А почему A003121 не взято в тег "oeis", он же специально для таких случаев существует? Ведь со ссылкой намного красивее: A003121

Спасибо! Забыл про эту возможность.

И не только про эту. Сумбурно дописывая разбор задачи уже глубокой ночью, забыл, например, обсудить появление оценки 286 для упорядочивания сумм чисел $a<b<c<d<e$, в которых допускаются суммы типа $a+a$. Это очередное возникновение числа 286 мне в ЛС уже мистикой назвали.
Никакой мистики!
С добавлением удвоенных исходных чисел сумм количество сумм возрастает с $\frac{n(n-1)}{2}$ до $\frac{n(n+1)}{2}$, т.е. до следующего треугольного числа. Учитывая упорядоченность исходных чисел получаем для сумм $n$ чисел точно такую же решетку, как для $n+1$ исходных чисел, но без сумм вида $a+a$.
Применяя правило сопоставления числам $1,2,\dots, {n+1\choose 2}$, записанным в треугольник, последовательностей сумм, получим в качестве оценки сверху $A003121(n+1)$. Но эта оценка будет еще менее точна, чем аналогичная для сумм без повторений. Ведь степеней свободы будет меньше (выбирать можно только $n$ чисел, а не $n+1$). Например, для $n=5$ получится 114, а не 244 возможных упорядочиваний.

[VAL]

Участники и болельщики, скачавшие решение ММ183 от Олега Полубасова!
По ошибке ведущего была выложена не та версия решения.
Убедительная просьба закачать файл обратно на форум и скачать правильный!