Олимпиада имени Леонарда Эйлера 2019-2020учебный год, II тур заключительного этапа

Дано натуральное число $n$. Множество $A$, составленное из натуральных чисел, таково, что для любого натурального числа $m$, не превосходящего $n$, во множестве $A$ есть число, делящееся на $m$. Какое наименьшее значение может принимать сумма всех элементов множества $A$? ( А. Кузнецов )

Комментарий/решение

Покажем, что сумма элементов $A$ равна $(k+1)+(k+2)+...+(2k+1) = \frac{(k+1)(3k+2)}{2}$ при $n=2k+1$ и $(k+1)+(k+2)+...+2k= \frac{k(3k+1)}{2}$ при $n=2k$. Покажем, что если у нас есть числа $b_{1} < b_{2} < ... < b_{k} < 2b_{1}$, то НОК$(b_{1}, b_{2}, ..b_{k}) > \sum \limits_{i=1}^{k}{b_{i}}$. Пусть НОК этих чисел $M=b_{1}n_{1}=a_{2}n_{2}=...b_{k}n_{k}$. Тогда $2n_{k}>n_{1}>...>n_{k} \Rightarrow n_{k}>k \Rightarrow M \geq ka_{k} \geq \sum \limits_{i=1}^{k}{b_{i}}$. Тогда в $A$ присутствуют элементы делящие числа от $[\frac{n}{2}]+1$ до $n$. А по тому утверждению что мы доказали выше их сумма не меньше суммы чисел от $[\frac{n}{2}]+1$ до $n$.