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

[grizzly]

rockclimber в сообщении #1346307 писал(а):

я - тот самый участник

А! Коллега по несчастью

rockclimber в сообщении #1346307 писал(а):

решить, убирать $3$ и $11$ или $33$

Думаю, если мы не стремимся искать все возможные решения для данного $n$, тогда можно смело убрать 33, а если вдруг этого станет мало -- ещё 8 и/или 27 (плюс 1, конечно). Я в этом не уверен, но если такой вариант упрощает программирование, можно попытаться так. Сомнительные случаи (я не думаю, что они будут) можно будет посмотреть отдельно.

[rockclimber]

Кажется, я придумал алгоритм. По крайней мере, он мне представляется намного более проработанным, чем то, что я обдумывал вчера.
Обозначения: простые числа, входящие в $(4n)!$ со степенями 2 и меньше - хвост. Максимальное простое число, входящее в степени 3 или больше - $t$. Большие числа - простые числа от $\sqrt{4n}$ до $t$ включительно. Маленькие числа - соответственно, все простые меньше $\sqrt{4n}$.
Алгоритм:
1. Считаем длину хвоста и:
1а. Если больше $n$ - группа не найдена, выходим.
1б. Если равно $n$ - проверяем все остальные множители. Если у всех показатели кратны 3 - группа найдена, выходим.
1в. Меньше $n$ - считаем остаток: $n$ минус длина хвоста.
2. Считаем количество лишних больших чисел и если оно
2а. Больше остатка из предыдущего шага - группа не найдена, выходим.
2б. Равно остатку - выбираем числа следующим образом:
2б-а. Если излишек каждого большого числа равен 1, выкидываем первые степени, группа найдена, выходим.
2б-б-1. Считаем излишки маленьких чисел. Варианты:
2б-б-1-а. Если все излишки - нулевые, к остатку двойки прибавляем 3.
2б-б-1-б. Если есть ненулевые излишки, составляем их список.
2б-б-2. Далее речь идет только о числах с излишками. Начиная с самого большого из больших, выкидываем числа по следующему принципу (текущее большое на данном шаге обозначим $D$, число из группы маленьких - $d$):
Самое большое $D$ умножаем на наименьшее $d$. Записываем список отдельно. Если большие числа кончились, а маленькие остались - докидываем самые маленькие из маленьких к наименьшим из больших. Контролируем уникальность этого списка, а также что получившиеся $D \cdot d^x < 4n$. Если это условие обеспечить невозможно, группа не найдена, выход. Если возможно - группа найдена, выход.
2в. Количество лишних больших чисел меньше остатка:
Тут почти все то же самое, что в п. 2б, но есть пара нюансов. Сейчас надо вылезти из-за компьютера, допишу позже.
Вроде бы, ничего не забыл.

[grizzly]

rockclimber
Думаю, должно сработать. Я не совсем понял пару моментов.
1. Мне показалось, что решение для $n=11$ не будет найдено из-за ошибочного выхода в 2б-а (или я не совсем понял, что значит "выходим").
2. Иногда может быть полезно выбросить квадрат малого числа. Например, 4 или 9. С другой стороны, вероятность того, что эта полезность будет критичной, кажется низкой.

В общем, можете не обращать внимания на эти замечания -- наверняка в процессе написания/отладки кода это всё автоматически пофиксится.

[rockclimber]

1. "Выходим" значит мы нашли ответ для данного $n$: либо мы сформировали 4-ю группу, либо обнаружили, что это невозможно.
Тут вы правы - я не учел, что уже на шаге 2б-а имеет значение количество остатков маленьких чисел. Надо немного переписать эту часть.
2. Да, такое тоже пришло в голову. Вероятность низкой не кажется. Я не считал пока, но кажется, что уже для $n=15$ такая ситуация возможна.

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

В общем, можете не обращать внимания на эти замечания -- наверняка в процессе написания/отладки кода это всё автоматически пофиксится.

Да нет, первое замечание очень полезное. Фактически, баг в алгоритме.

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

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

Думаю, если мы не стремимся искать все возможные решения для данного $n$, тогда можно смело убрать 33, а если вдруг этого станет мало -- ещё 8 и/или 27 (плюс 1, конечно).

неправильно (если я понял вашу мысль).
Для трех чисел вместо набора $1 + 8 + 27 = 36$ лучше взять $4 + 6 + 9 = 19$.
Но тут я другую хитрость придумал. Заранее приготовить список, какие множители выбирать для какого количества чисел. То есть если нужно выкинуть 1 число - это 1, если 2 - то 1 и 8, если 3 - то 4, 6, 9, и так далее. Этот список не будет зависеть от $n$.

-- 16.10.2018, 01:06 --

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

Иногда может быть полезно выбросить квадрат малого числа. Например, 4 или 9.

Пока я отсутствовал, придумал искусственный пример. Допустим, у нас 2 лишних множителя 59 и 2 лишних множителя 3, из которых нужно сформировать 3 числа. Вместо $3 + 59 + 59 \cdot 3 = 239$ можно взять $ 59 + 59 \cdot 2 + 2 \cdot 2 \cdot 3 \cdot 3 = 213$.
Честно говоря, уже и не знаю, как все это впихнуть в программу.

[rockclimber]

Короче, все на самом деле намного проще оказалось. После некоторых размышлений и пары экспериментов на реальных примерах (кстати, оказывается, при том, что существуют решения для $n=10$ и $n=11$, следующее решение существует только для $n=15$) запутанный алгоритм выше (весь путь я уже не вспомню, да уже и не важно) плавно превратился в простой и изящный:
До шага 2а все остается от предыдущего алгоритма...
2б. Если количество лишних больших чисел меньше или равно количеству оставшихся мест (обозначим $m$) в группе 4:
3. Выписываем все излишки для всех чисел по убыванию, например: $19, 17, 17, 13, 11, 3, 3, 2$
4. Выбираем из этого списка первые $m$ чисел.
5. Оставшиеся числа записываем напротив в обратном порядке ("змейкой"). Например, если в примере выше нам осталось 4 получить 4 числа, то записать так: $19 \cdot 2, 17 \cdot 3, 17 \cdot 3, 13 \cdot 11$. Если получились дубликаты, сделать обмен с числом справа, то есть $19 \cdot 2, 17 \cdot 3, 17 \cdot 11, 13 \cdot 3$.
6. Если перестановками удалить дубликаты не удалось, к концу списка чисел добавляем три двойки и перераспределяем числа еще раз следующим способом:
Первые $m$ чисел остаются те же: $19, 17, 17, 13$
Затем: $11, 3, 3, 2, 2, 2, 2$.
7. С этим хвостом проделываем операцию, аналогичную шагу 5: $(11, 3, 3, 2, 2, 2, 2) \to (11, 3 \cdot 2, 3 \cdot 2, 2 \cdot 2) \to (11, 6, 6, 4)$ При необходимости - сортируем, возвращаемся к шагу 5.
Получается как бы такая "змейка", которая схлопывается от хвоста к голове.

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

Конечно, еще остаются нюансы, но в таком виде алгоритм существенно проще для программирования.

[VAL]

rockclimber в сообщении #1346634 писал(а):

Короче, все на самом деле намного проще оказалось. После некоторых размышлений и пары экспериментов на реальных примерах (кстати, оказывается, при том, что существуют решения для $n=10$ и $n=11$, следующее решение существует только для $n=15$)

Обидно, что даже участники Марафона не читают разбор конкурсных задач. Для кого же я стараюсь?!

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

Среди $n$, меньших $n_0$ требуемое разбиение возможно для $n \in \{10,11,14,15,18,20,22,23,24,25,26\}$

Вот разбиение для $n=14$:

        {1, 5, 7, 17, 20, 21, 22, 24, 25, 27, 32, 52, 54, 56}

        {2, 9, 10, 12, 13, 14, 16, 18, 30, 34, 40, 44, 45, 49}

         {3, 4, 6, 8, 11, 15, 26, 28, 35, 36, 42, 48, 50, 51}

       {19, 23, 29, 31, 33, 37, 38, 39, 41, 43, 46, 47, 53, 55}

rockclimber писал(а):

Строгого доказательства правильности этого алгоритма у меня нет

Я бы удивился, если бы оно у Вас было

[rockclimber]

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

Обидно, что даже участники Марафона не читают разбор конкурсных задач. Для кого же я стараюсь?!

Я читал. Но увлекся построением своего алгоритма и забыл. Да и вообще, вы сами видели, сколько у вас чисел в том посте? Все не упомнишь.
А потом проверял свой алгоритм и ошибся, потому что вручную считал и не ту циферку переписал с экрана. Если переписать правильно, то мой алгоритм находит ответ.

-- 16.10.2018, 17:26 --

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

rockclimber писал(а):

Строгого доказательства правильности этого алгоритма у меня нет

Я бы удивился, если бы оно у Вас было

А это вообще возможно? Доказать, что алгоритм правильный или найти в нем ошибку?

[grizzly]

Сделал очень грубую прикидку на Вольфраме для 6-групп. Получилась, оценка для $n$ порядка 9 000.

[rockclimber]

rockclimber в сообщении #1346572 писал(а):

Для трех чисел вместо набора $1 + 8 + 27 = 36$ лучше взять $4 + 6 + 9 = 19$.
Но тут я другую хитрость придумал. Заранее приготовить список, какие множители выбирать для какого количества чисел. То есть если нужно выкинуть 1 число - это 1, если 2 - то 1 и 8, если 3 - то 4, 6, 9, и так далее. Этот список не будет зависеть от $n$.

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

$1 \to 1$

$2 \to 2, 4$

$3 \to 1, 2, 4$

$4 \to 1, 2, 4, 8$

$5 \to 1, 2, 3, 4, 9$

$6 \to 1, 2, 3, 4, 8, 9$

Ну и так далее.

[rockclimber]

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

Сделал очень грубую прикидку на Вольфраме для 6-групп. Получилась, оценка для $n$ порядка 9 000.

У меня что-то вроде того же получается.
У меня как-то тяжело идет написание моего алгоритма, куча всяких нюансов, на которые я постоянно натыкаюсь, но промежуточная версия может оценить уже для каждого числа возможность разбиения.
Программа выдает результат "решение возможно", если для данного $n$ выполняются следующие условия:
количество чисел в "хвосте" (это простые числа, входящие в $(4n)!$ со степенями, меньше $k-1$ ) плюс количество излишков больших чисел (это простые числа больше $\sqrt{4n}$, но не входящие в "хвост") меньше или равно $n$.
Пока найдено следующее ($k=4$ не интересно, интересно дальше):
$k=5$: решения возможны при $n=436, 439, 440, 441$, далее, видимо, везде.
$k=6$: решения возможны при $n=8615, 8620 - 8627, 8632, 8633$, дальше я бы предположил еще пропуски, проверю попозже.
$k=7$: при $n < 31000$ решений нет, программа все еще работает. Проверка будет идти до $n=300000$, но с такими темпами раньше завтрашнего утра я бы результатов не ждал.
Еще можно посмотреть на скорость роста $n_{min}$ в зависимости от $k$:

$k = 4, n_{min} = 10$

$k = 5, n_{min} \sim 440$

$k = 6, n_{min} \sim 9000$

Я бы не ожидал решения для $k=7$ меньше $100 000$.

[rockclimber]

Для $k=7$ решения начинаются где-то после $n=157433$.

[VAL]

===========ММ237===============

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

Студент математического факультета Вася Пупкин написал на доске некоторую перестановку $A$ из $S_{10}$ в виде произведения независимых циклов (запись каждого цикла начинается с наименьшего элемента; опускались ли в записи циклы длины 1 - неизвестно). Васины однокурсники прокомментировали эту запись.

Аня: $A^6$ – тождественная перестановка.
Ваня: Длины всех циклов $A$ – числа Фибоначчи.
Даня: В $S_{10}$ существует ровно 3 перестановки, квадрат которых равен $A$.
Маня: Хм, уравнение $X^2=B$ не может иметь в $S_{10}$ ровно 3 решения ни при каком $B$.
Саня: Более того, количество решений уравнения $X^2=B$ в $S_{10}$ не может быть нечетным ни при каком $B$.
Таня: Квадрат наибольшего элемента в самом длинном цикле меньше порядка $A$.
Зина: $A^5$ имеет столько же циклов, сколько и $A$
Лина: Внутри всех циклов элементы строго возрастают.
Нина: Произведение всех элементов одного из циклов кратно произведению всех элементов более длинного цикла и сумме всех элементов более короткого.
Фаина: Зина, Лина и Нина правы.

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

Решение

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

(Решение vpb)

Решение задачи ММ237.

Имеет место такое
Предложение. Пусть $g\in S_n$. Если длины циклов в $g$ --- различные нечетные числа, то уравнение $x^2=g$ имеет ровно одно решение. Во всех остальных случаях решений или нет, или их четное число.

(Доказательство этого предложения дадим в конце решения).

Отсюда сразу вытекает, что Даня и Саня неправы (рассмотрим элемент со структурой циклов $9+1$ или $7+3$), а Маня права. Значит, среди всех утверждений не более 8 верных, и не менее 1.

Отметим, что если нет циклов длины 5, то Зина права, а иначе нет (при возведении в 5-ю степень цикл длины 5 пропадает, а цикл другой длины превращается в другой цикл той же длины).

Допустим, что есть 8 верных утверждений. Тогда все, кроме Дани и Сани, правы, значит $A^6=1$. С другой стороны, длина наибольшего цикла должна быть $8$, что противоречит $A^6=1$.

Допустим, что верных утверждений 7. Тогда длина наибольшего цикла --- 7, откуда $A^6\ne1$, и $7$ также не есть число Фибоначчи, и поэтому Аня и Ваня неправы. Значит, верных утверждений не более 6, противоречие.

Допустим, верных утверждений не более 3. Тогда длина наибольшего цикла не более 3. Поэтому Аня, Ваня и Зина правы, а также и Маня, значит есть $\geq4$ верных утверждения, противоречие.

Итак, верных утверждений может быть 4, 5, или 6.

Рассмотрим возможность, когда верных утверждений 4, и, следовательно, наибольший цикл имеет длину 4. Очевидно, в этом случае Аня и Ваня неправы. Кроме того, порядок $A$ не превосходит ${\rm HOK}(2,3,4)=12$. Но квадрат наибольшего элемента в любом 4-цикле $\geq16$, поэтому Таня неправа. Зина же права. Следовательно, среди Лины, Нины и Фаины --- ровно двое правых. Но этого быть никак не может. Действительно, если Лина или Нина не правы, то и Фаина тоже неправа, значит среди них троих правых $\leq1$. Если же Лина и Нина правы обе, то и Фаина права, значит правы все трое. Двух не получается ни при каком раскладе.

Теперь рассмотрим случай, когда верных утверждений 6. Тогда наибольший цикл --- длины 6. Значит, Ваня неправ, а Зина права. Заметим, что квадрат наибольшего элемента в 6-цикле всегда $\geq36$. С другой стороны, элемент, содержащий 6-цикл, имеет порядок не более 12. Поэтому Таня неправа. Значит, все остальные, кроме Дани, Сани, Тани и Вани, правы. В частности, $A^6=1$. Поскольку Нина права, есть по крайней мере три различных длины цикла. Поэтому структура циклов есть $6+3+1$ или $6+2+1+1$. Допустим, что $6+2+1+1$. Тогда произведение элементов из 2-цикла кратно произведению элементов из 6-цикла. Но первое из этих произведений $\leq90$, а второе $\geq720$, противоречие. Следовательно, структура циклов
$6+3+1$. Теперь заметим, что произведение элементов в 3-цикле может быть $\geq720$, только если его элементы суть $8,9,10$. Но тогда оставшийся цикл --- это $(7)$. Однако $720$ не кратно $7$. Итак, случая, когда верных утверждений 6, быть тоже не может.

Таким образом, верных утверждений 5. Значит, Зина неправа, и Аня тоже. Поскольку Зина неправа, то и Фаина неправа. Все оставшиеся --- Ваня, Маня, Таня, Лина и Нина --- должны быть правы. Поэтому есть по крайней мере три различных длины цикла, и все длины циклов --- числа Фибоначчи. Значит, возможные структуры циклов суть $5+3+2$, или $5+3+1+1$, или $5+2+2+1$, или $5+2+1+1+1$. Квадрат наибольшего элемента в самом длинном цикле --- по крайней мере $\geq25$, поэтому порядок перестановки $\geq 26$. Этому ограничению удовлетворяет только структура циклов $5+3+2$. Порядок в таком случае равен $30$, значит наибольший элемент в 5-цикле не превосходит $5$, значит 5-цикл содержит в точности элементы $1,2,3,4,5$.
Произведение всех элементов 3-цикла кратно $5!=120$, и сумме двух элементов из 2-цикла. Это возможно, только если элементы в 3-цикле суть $6,8,10$, а в 2-цикле $7,9$. Наконец, ввиду условия, что в каждом цикле цифры возрастают, получаем $A=(1,2,3,4,5)(6,8,10)(7,9)$.

Ответ: $A=(1,2,3,4,5)(6,8,10)(7,9)$.

В заключение следует обосновать предложение. Прежде всего, если $g$ --- элемент описанного специального вида, то довольно ясно, что квадратный корень из $g$ единственен.

Допустим, что $g$ не имеет такого вида. Покажем, что в этом случае уравнение $x^2=g$ необходимо имеет четное число решений.

Прежде всего допустим, что порядок $m=|g|$ четен. Тогда $z=g^{m/2}$ --- элемент порядка 2. Очевидно, что $g$, и потому $z$, коммутирует с любым элементом $x$ таким, что $x^2=g$. Поэтому для любого такого элемента $(xz)^2=x^2z^2=g\cdot1=g$. Следовательно, множество всех $x$ с $x^2=g$ оказывается объединением смежных классов по подгруппе $\{1,z\}$, и потому имеет четный порядок.

Теперь пусть $m=|g|$ нечетен. Тогда $g$ содержит $\geq2$ циклов одной и той же нечетной длины. Отсюда следует, что существует элемент $h\in S_n$ такой, что $h^2=1$ и $hg=gh$. Откуда, в свою очередь, видим, что порядок подгруппы

$$ C=C_G(g)=\{y\in G\mid gy=yg\} $$

четен. (Отметим еще раз, что все искомые элементы $x$ лежат в $C$.)

Рассмотрим элемент $g_1=g^l$, где $l=(m+1)/2$. Тогда $g_1\in Z(C)$. Очевидно также, что $g_1^2=g$. Поэтому для любого $x$ такого, что $x^2=g$ элемент $x_1=g_1^{-1}x$ удовлетворяет соотношению $x_1^2=g_1^{-2}x^2=g^{-1}g=1$. Наоборот, если $x_1\in C$ и $x_1^2=1$, то для $x=g_1x_1$ имеем $x^2=g_1^2x_1^2=g\cdot1=g$. Значит, искомые элементы $x$ взаимно однозначно соответствуют элементам $x_1\in C$ таким, что $x_1^2=1$. Но таких элементов четное число,
в силу классической теоремы Фробениуса: Если $G$ --- конечная группа, и $n$ делит $|G|$, то число решений уравнения $x^n=1$ в $G$ делится на $n$.
(См. М. Холл, Теория групп, гл.9, пар.1.)

(Конечно, предложение можно было бы доказать и более комбинаторными рассуждениями, специально приспособленными к группе $S_n$).

Обсуждение

Естественно конкурсанты начали решение с проверки утверждений Мани и Сани, истинность которых не зависит от записанной на доске перестановки.
Причем проверка утверждения Мани оказывается наиболее сложной частью задачи. Некоторые участники предпочли ограничиться доказательством отсутствия трех решений уравнения $X^2=B$ в $S_{10}$, другие же рассмотрели более общий вопрос о возможных количествах решений этого уравнения. Наконец, еще один участник привел чисто алгебраическое обоснование правоты Мани.
Ведущий пошел по пути "других" (комбинаторщиков), но для надежности проверил свои теоретические выкладки возведением всех элементов $S_{10}$ в квадрат (разумеется, не руками). Конкурсанты оказались более уверенными в себе и к мощи компа не прибегали (некоторые - зря ).
Дальнейшие рассуждения практически все вели, перебирая возможные длины наибольшего цикла. И только Влад Франк отталкивался от истинности или ложности утверждения Фаины, показав, что этот путь тоже ведет к верному ответу.

Увлекшись обобщениями вопроса о количестве решений уравнения $X^2=B$ в $S_{10}$, я доказал, что для любого простого $p$ и любого $n$ уравнение $X^p=B$ имеет либо единственное решение, либо количество его решений кратно $p$ (для составных показателей это уже не так).
Не остановившись на достигнутом, я вывел общую формулу для количества решений уравнения $X^k=B$ в $S_n$ (понятно, что ответ зависит от цикловой структуры $B$). Конечно, я понимал, что вряд ли являюсь первопроходцем: уж больно классический объект и слишком естественна постановка задачи. Но всерьез гуглить начал лишь только получив результат. Разумеется, у меня нашлись предшественники. Причем, насколько мне удалось установить, первая работа с ответом на этот вопрос была на русском языке (хотя я старательно формулировал запрос на английском): http://www.mathnet.ru/php/archive.phtml ... n_lang=eng

Приведу все возможные количества решений $X^k=B$ в $S_n$ для небольших $k$ и $n$.

k = 2
1 {1}
2 {0, 2}
3 {0, 1, 4}
4 {0, 1, 2, 10}
5 {0, 1, 2, 26}
6 {0, 1, 4, 76}
7 {0, 1, 2, 4, 8, 10, 232}
8 {0, 1, 2, 4, 8, 12, 20, 26, 764}
9 {0, 1, 2, 4, 10, 12, 16, 52, 76, 2620}
10 {0, 1, 2, 4, 6, 8, 10, 24, 26, 40, 152, 232, 9496}

k = 3
1 {1}
2 {1}
3 {0, 1, 3}
4 {0, 1, 9}
5 {0, 1, 3, 21}
6 {0, 1, 9, 81}
7 {0, 1, 3, 9, 21, 351}
8 {0, 1, 3, 9, 33, 81, 1233}
9 {0, 1, 3, 9, 18, 21, 27, 33, 351, 5769}
10 {0, 1, 3, 9, 18, 21, 33, 81, 1233, 31041}

k = 4
1 {1}
2 {0, 2}
3 {0, 1, 4}
4 {0, 1, 16}
5 {0, 1, 2, 56}
6 {0, 1, 4, 256}
7 {0, 1, 2, 4, 16, 1072}
8 {0, 1, 4, 8, 48, 56, 6224}
9 {0, 1, 2, 10, 16, 256, 33616}
10 {0, 1, 2, 4, 6, 10, 56, 64, 96, 1072, 218656}

k = 5
1 {1}
2 {1}
3 {1}
4 {1}
5 {0, 1, 25}
6 {0, 1, 145}
7 {0, 1, 25, 505}
8 {0, 1, 25, 145, 1345}
9 {0, 1, 25, 145, 505, 3025}
10 {0, 1, 25, 145, 385, 505, 1345, 78625}

k = 6
1 {1}
2 {0, 2}
3 {0, 6}
4 {0, 2, 18}
5 {0, 1, 2, 66}
6 {0, 1, 4, 396}
7 {0, 1, 2, 12, 2052}
8 {0, 1, 4, 6, 12, 36, 12636}
9 {0, 2, 4, 12, 18, 132, 91548}
10 {0, 2, 6, 8, 18, 24, 66, 792, 625176}

Поясню, как я реагировал на ошибки при подсчете возможных количеств решений уравнения $X^2=B$ в $S_{10}$.
Фатальная ошибка (вместо самих решений считалось лишь возможное количество их цикловых видов), приведшая к "опровержению" утверждения Маши, разумеется, нарушила весь дальнейший ход решения и была отражена в оценке.
Автору неверных комбинаторных формул при подсчете количеств решений повезло больше. Одно решение при этом не исчезло, а три не появилось. Поэтому дальнейшая цепочка рассуждений привела к верному ответу. Но оставить ошибки на промежуточных шагах без внимания я, конечно, не мог.
Наконец, локальные арифметические ошибки, не повлиявшие на решения я вовсе не учитывал. Пример такой ошибки есть в приведенном решения Анатолия Казмерчука (там, где у Анатолия получилсь 18 решений должно быть 24). В самом деле, 18 получается как сумма двух слагаемых, одно из которых подсчитано верно и равно 12. Понятно, что сумма при этом будет больше 3, что собственно и требовалось. Поэтому данная вычислительная ошибка в принципе не могла повлиять на ход решения.
Неполный балл у Константина Шамсудтинова связан не с ошибками, а с недостаточно подробным изложением решения. Обосновав верную оценку утверждений Сани и Мани, Константин написал, что дальнейшее очевидно и привел правильный ответ.

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

Награды

За решение задачи ММ237 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 10;
vpb - 8;
Виктор Филимоненков - 7;
Владислав Франк - 7;
Константин Шамсутдинов - 6.
Валентина Колыбасова - 5;
Евгений Гужавин - 2;

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

[VAL]

===========ММ238===============

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

Вася написал на доске $k$ последовательных натуральных чисел и нашел их НОК - $V$.
Петя написал $k$ последовательных натуральных чисел, больших Васиных, и тоже нашел их НОК - $P$.
Оказалось, что $2018 < \frac VP < 2019$. При каком наименьшем $k$ такое возможно?

Решение

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

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

ММ238

Вася написал на доске $k$ последовательных натуральных чисел и нашел их НОК - $V$.
Петя написал $k$ последовательных натуральных чисел, больших Васиных, и тоже нашел их НОК - $P$.
Оказалось, что $2018 < \frac VP < 2019$. При каком наименьшем $k$ такое возможно?

Эстетическая оценка 4,5 балла. Задача тоже относится к тому типу, который мне по душе. Но тоже показалась слишком простой для лобового решения.
____________

Ответ: при $k=11$. Пример: числа Васи -- 11 чисел, начинающихся с 787837, числа Пети начинаются с 803880.

Решение.
Произведение Петиных чисел больше, чем Васиных. Единственное, за счёт чего можно увеличивать $\frac VP$ -- сэкономить на повторении одних и тех же простых (будем говорить о простых -- для удобства) сомножителей в наборе Петиных чисел.

Сформулируем несколько очевидных утверждений.

-- У $k$ последовательных чисел могут повторяться (присутствовать у разных чисел) только сомножители, меньшие $k$. На всех этих сомножителях, кроме делителей $k,$ можно сэкономить (на делителях $k$ в определённых случаях можно сэкономить, но только в меньшей степени, для решения это не пригодится).
-- С целью сэкономить набор Пети можно начинать с числа, кратного $(k-1)!$, а набор Васи подобрать так, чтобы остаток по модулю каждого экономлящего $p_i$ был равен 1 -- например начинать с числа вида $s(k-1)!+1$.
-- Если $k/p<p^n<k$, то сэкономить можно не более чем на $p^n$, а остальные делители вида $p^m, m<n$ сократятся в лучшем случае в одинаковом количестве в каждом наборе (в других случаях выигрыш может быть меньше).

Таким образом, максимально возможное значение дроби $\frac VP$ для данного $k$ (обозначим его через $M_k$) будет не больше произведения $2^{i_1}3^{i_2}...p_s^1$, где каждый из сомножителей вида $p^j$ меньше $k$.

Поскольку Петины числа больше Васиных, $\frac VP$ будет всегда меньше $M_k$, но может неограниченно приближаться к нему. Вообще, множество значений этой дроби будет всюду плотным на отрезке $[0;M_k]$.

Осталось посмотреть по описанному алгоритму, чему равно $M_k$ для разных $k$.

$$ M_2=1, \quad M_3=2, \quad M_4=3, \quad M_5=12, \quad M_6=10, \quad M_7=60, $$

$$ M_8=105, \quad M_9=280, \quad M_{10}=252, \quad M_{11}=2520 $$

Конкретный пример решения я подобрал руками, не претендуя на какую-либо его логичность / оптимальность (просто наращивал кратность множителя 2520, так показалось проще/быстрее). В $M_6$ и $M_{10}$ множитель 2 входит со степенями 1 и 2. Если аргументация выше недостаточна для объяснения этого, тогда я добавлю, что даже при вхождении с максимальными степенями 2 и 3 это не может повлиять на ответ задачи.

Обсуждение

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

Говоря о тяжеловесном подходе я имел в виду то, как многие конкурсанты оценивали $\frac{M_k}{m_k}$, где $M_k$ - максимальное значение отношения произведения $k$ последовательных чисел к их НОК, а $m_k$, соответственно, минимальное.
Наиболее простым мне показался метод, примененный Владиславом Франком (правда, применяя его Влад пару раз обсчитался
Проиллюстрирую подход Влада на примере нахождения $\frac{M_9}{m_9}$: Среди девяти последовательных чисел ровно три кратно 3 и ровно одно кратно 9. Поэтому множитель 3 не войдет в искомое отношение. Однако туда войдут множители 5 и 7, так среди 9 последовательных чисел может быть как два, так и одно кратное 5 (7). Наконец, если произведение девяти чисел начинается с числа кратного 8, то его отношение к НОК будет в 8 раз больше, чем в случае, когда произведение начинается с нечетного числа. Итого $\frac{M_9}{m_9}=280$.

Только один из конкурсантов заметил (по крайней мере, только один отметил), что $\frac{M_k}{m_k}$ равно $\frac{LCM(1,2,\dots,k)}k$ (A002944).

Некоторые участники не стали приводить примеров Васиных и Петиных чисел (если при этом существование таких чисел было строго обосновано, баллы не снимались), другие же - привели, ни разу при этом не повторившись.
Минимальный пример приведен в решении Анатолия Казмерчука. Васины числа начинаются с 21169, а Петины с 21600. По-видимому, это наименьшие подходящие числа. По крайней мере, в авторском решении фигурируют именно они. А я, кажется, искал именно наименьшие. Впрочем, задача составлялась в апреле и подробности я уже забыл, а в сохранившемся maple-документе нет ни одного комментария

Награды

За решение задачи ММ238 участники Марафона получают следующие призовые баллы:
Анатолий Казмерчук - 7;
vpb - 7;
Виктор Филимоненков - 7;
Владимир Чубанов - 7;
Евгений Гужавин - 7;
Владислав Франк - 6;
Константин Шамсутдинов - 6;
Владимир Дорофеев -5.

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

[JohnDou]

А как поучаствовать в марафоне? И нет ли pdf'a со всеми задачами? (и решениями?)

[rockclimber]

JohnDou в сообщении #1350043 писал(а):

А как поучаствовать в марафоне?

1. Прочитать топик «Математический марафон»
2. Расписаться в журнале по технике безопасности при проведении математических вычислений.