Задача 7. Делимость сумм выбранных чисел

Одинаковые остатки

Пусть $p$ — одно из чисел $2, 3, 5, 7$, и сумма любых $p$ чисел набора делится на $p$. Возьмём любые два числа $x$ и $y$ и ещё $p - 1$ других чисел (их хватает: всего чисел $20 > p$). Суммы «эти $p - 1$ чисел плюс $x$» и «они же плюс $y$» делятся на $p$, значит, и их разность $x - y$ делится на $p$. Итак, все $20$ чисел дают одинаковый остаток при делении на $p$.

Обратно: если все числа дают остаток $r$, то сумма любых $p$ из них даёт остаток $p \cdot r$, то есть делится на $p$.

Остаток при делении на 210

Разность любых двух чисел делится на $2, 3, 5$ и $7$, а значит, и на $2 \cdot 3 \cdot 5 \cdot 7 = 210$ (числа попарно взаимно просты). Поэтому все числа дают один и тот же остаток $m$ при делении на $210$, $1 \leqslant m \leqslant 209$. Ни одно число не делится на $2, 3, 5, 7$ ⇔ на них не делится $m$ (число и $m$ отличаются на кратное $210$).

Оценка суммы

Упорядочим числа: $x_1 < x_2 < \ldots < x_{20}$. Все они дают остаток $m$, поэтому соседние отличаются хотя бы на $210$, и $x_i \geqslant m + 210(i - 1) \geqslant 1 + 210(i - 1)$. Сумма

Пример

Числа $1, 211, 421, \ldots, 1 + 19 \cdot 210 = 3991$ дают остаток $1$ при делении на $210$: ни одно не делится на $2, 3, 5, 7$, и по шагу 1 все суммы делятся как нужно. Их сумма ровно $39\,920$. Значит, наименьшее значение — $39\,920$.