Наименьшее возможное значение НОК

[Ktina]

Сумма десяти натуральных чисел равна 2018. Какое наименьшее значение может принимать их НОК?

[Someone]

$224$

[DanilovV]

5 (?)

[arseniiv]

DanilovV
Одно из чисел обязательно не меньше 202, а НОК не меньше его.

[DanilovV]

arseniiv Все смешал. Сразу не понял, что получил. Спасибо.

[Dendr]

Обозначим искомое минимальное НОК, как $M(n,S)$. Очевидно, что если $S$ кратно $n$, то ответ $\frac{S}{n}$.

Рассмотрим некоторое разложение $S$ на $n$ слагаемых. Пусть $p$ - НОД этих слагаемых, тогда:
1) их НОК равен НОДу, помноженому на НОК чисел, полученных от деления слагаемых на НОД
2) $p$ - делитель $S$.

Так мы сводим задачу к поиску минимуму величины $LCM(\frac{S}{q}, M(n,q))$ по всем $q$. Здесь $q\geqslant n$ - делители S.

Среднее арифметическое чисел равно $\frac{q}{n}$, и их НОК не меньше этого среднего при любом разложении. В том числе и минимальный НОК. То есть $M(n,q)\geqslant\frac{q}{n}$, поэтому чем меньше q, тем лучше. Строгого критерия здесь не находится, особенно если простые делители в $S$ встречаются несколько раз. Поэтому пока просто будем иметь это в виду.
Таким образом, меньшие НОК получаются, если брать делители $S$, большие $n$, но как можно меньше.

Так как НОД слагаемых теперь равен 1, то рассмотрим наименьшее из них - $b$. Оно взаимно простое с НОДом всех остальных по построению. Поэтому НОК равно произведению числа $b$ на НОК остальных. Так что $M(n,q)=b\cdot M(n-1,q-b)\geqslant b\geqslant \frac{q-b}{n-1}\geqslant b\cdot \frac{q-b+1}{n}$. Второй множитель с ростом $b$ убывает медленно, зато второй - быстро растет, так что следует брать единицу. Но тогда $M(n,q)=M(n-1,q-1)$.

Тогда, $M(n,S)=\fraq{S}{q}\dot M(n-1,q-1)\geqslant\frac{S(q-1)}{q(n-1)}\approx\frac{S}{n-1}$. И вот мы получили рекуррентную формулу и не забываем, что имеется в виду минимум по всем допустимым делителям суммы. Начинать переборы, как видно, следует с наименьшего делителя, попутно обращая внимание на то, что в какой-то момент среднее превысит уже найденное значение минимального НОК.

К цифрам.
2018 раскладывается на два простых - 2 и 1009. Давайте выберем $q=1009$:
$M(10,2018)=2\cdot M(9,1008)$.
Повезло: 1008 делится на 9 нацело. В частном получится 112, и ответ - 224.
Мы также могли взять $q=2018$: $M(10,2018)=M(9,2017)>224.11$ - то есть сразу за пределами.
Чтобы исключить что-то пропущенное в изложении выше, проверим другое значение минимального слагаемого, учтя, что НОД теперь не равен 2, то есть есть хотя бы одно нечетное. Тогда любое слагаемое взаимно просто с НОК остальных.
$2018=b+a_1+...+a_9$, НОК равен $b\cdot A$, где НОК девяти слагаемых $A\geqslant \frac{2018-b}{9}$.
Эта функция возрастает при $b$ от 0 до 1009, так что наименьшее ее значение достигается при единице и равно 224,111. Так что этот случай не годится.

Почему были сделаны оговорки о переборе выше? Почему нельзя просто взять наименьшее допустимое $q$? Рассмотрим задачу $M(7,250)$.
Допустимые значения $q$: 10, 25, 50, 125, 250.
Для 10: $M(7,250)=25\cdot M(7,10)=25\cdot M(6,9) = 25\cdot M(5,8) = 25\cdot M(4,7) = 25\cdot M(3,6)=50 $
Для 25: $M(7,250)=10\cdot M(7,25)=10\cdot M(6,24)= 40$. Если бы мы ограничились предыдущим случаем, упустили бы минимальный.
Для 50: $M(7,250)=5\cdot M(7,50)=5\cdot M(6,49)\geqslant5\cdot\frac{49}{6}=40.833$ Вот теперь мы можем законно не смотреть дальше.