Задание 6963E1

Минимальная сумма 100 различных натуральных чисел: $1+2+\ldots+100 = 5050$. Нам нужно получить сумму $5120$, то есть добавить $70$.

а) Если есть число $230$, то сумма остальных 99 чисел равна $5120-230=4890$.
Минимальная сумма 99 различных натуральных чисел: $1+2+\ldots+99 = 4950$.
Так как $4950 > 4890$, такой набор невозможен.

б) Если числа $14$ нет, то минимальный набор из 100 чисел: $1,2,\ldots,13,15,16,\ldots,101$.
Его сумма: $(1+2+\ldots+101) - 14 = 5151 - 14 = 5137$.
Так как $5137 > 5120$, число $14$ обязательно.

в) Пусть $k$ — количество чисел, кратных $14$. Число $14$ уже есть по пункту (б).
При $k=1$ (только число $14$): оставшиеся 99 чисел — минимальные, не кратные $14$. Их сумма: $(1+2+\ldots+100) - (14+28+42+56+70+84+98) + (101+102+103+104+105+106+107)$. Вычисление показывает, что сумма превышает $5120$, поэтому $k=1$ невозможен. Аналогично, $k=2$ и $k=3$ также дают сумму больше $5120$.

Проверим $k=4$. Возьмём наименьшие 4 числа, кратные $14$: $14, 28, 42, 56$. Их сумма: $140$.
Остальные 96 чисел — наименьшие, не кратные $14$, начиная с $1$. Их сумма (без чисел $14,28,42,56,70,84,98$) с заменой на следующие за $100$): $5050 - (14+28+42+56+70+84+98) + (101+102+103+104+105+106+107) = 5050 - 392 + 728 = 5386$. Но это сумма 103 чисел (96+7 замен). Нужно оставить 96 чисел. Правильный расчёт: возьмём 96 наименьших, не кратных $14$. Это числа от $1$ до $100$, исключая $14,28,42,56,70,84,98$ (7 чисел), и добавим $101,102,103,104,105,106$ (6 чисел), чтобы получить 96 чисел. Их сумма: $5050 - (14+28+42+56+70+84+98) + (101+102+103+104+105+106) = 5050 - 392 + 621 = 5279$. Тогда общая сумма для $k=4$: $5279 + 140 = 5419$, что больше $5120$. Значит, нужно уменьшать другие числа.

Минимальная сумма при $k=4$ достигается, если взять сами числа, кратные $14$, как можно меньше ($14,28,42,56$), а остальные 96 чисел — наименьшие возможные, не кратные $14$, но так чтобы общая сумма была $5120$. Поскольку минимальная сумма 100 различных натуральных чисел $5050$, а нам нужно $5120$, запас $70$ позволяет немного увеличивать числа. Подбор показывает, что можно добиться суммы $5120$ при $k=4$. Например, можно взять числа: $14,28,42,56$ и остальные — наименьшие, начиная с $1$, но некоторые из них увеличить, чтобы компенсировать избыток суммы. Конструктивно: если взять 96 наименьших не кратных $14$ чисел (как в шаге 5), их сумма $5279$, плюс кратные $14$ дают $5419$, что на $299$ больше $5120$. Чтобы уменьшить сумму на $299$, можно заменить некоторые из добавленных чисел ($101-106$) на меньшие, но не кратные $14$ и не совпадающие с уже выбранными. Это возможно. Следовательно, $k=4$ достижимо.

При $k=5$: наименьшие кратные $14$: $14,28,42,56,70$. Их сумма: $210$. Тогда остальные 95 чисел — наименьшие не кратные $14$. Их сумма будет ещё больше, чем в случае $k=4$, и общая сумма будет ещё больше $5120$, но запас в $70$ позволяет уменьшать числа. Однако, если $k=5$, то чисел, кратных $14$, больше, что увеличивает минимальную возможную сумму набора. Проверка минимальной суммы при $k=5$: кратные $14$: $14,28,42,56,70$ (сумма $210$). Не кратные $14$: наименьшие 95 чисел, начиная с $1$, исключая $14,28,42,56,70,84,98$ (исключаем 7 чисел, но $70$ уже взято, поэтому исключаем ещё $84,98$). Берём числа от $1$ до $100$, исключая $14,28,42,56,84,98$ (6 чисел), и добавляем $101,102,103,104,105$ (5 чисел), чтобы получить 95 чисел. Сумма не кратных: $5050 - (14+28+42+56+84+98) + (101+102+103+104+105) = 5050 - 322 + 515 = 5243$. Общая сумма: $5243+210=5453$, что на $333$ больше $5120$. Уменьшить на $333$ за счёт замены добавленных чисел ($101-105$) на меньшие возможно, но нужно убедиться, что не нарушается условие кратности и различности. В принципе, это возможно, так как запас для манёвра есть. Но вопрос о наименьшем $k$. Мы уже показали, что $k=1,2,3$ невозможны (дают сумму больше $5120$ при минимальном наборе). Для $k=4$ мы показали достижимость. Значит, наименьшее $k$ равно $4$.