Задача М1222‍‍

а) Рассмотрим все возможные «не алгебраические» (т. е. без минусов) суммы, которые можно составить из $s+1$‍‍ чисел. Их количество равно $2^{s+1}-1\gt m-1$‍.‍ (Каждую сумму можно задать последовательностью длины $s+1$‍‍ из нулей и единиц, в которой на $i$‍‍-м месте стоит 1, если в сумму входит $i$‍‍-е число; количество последовательностей равно $2^{s+1}$‍,‍ последовательность из одних нулей надо исключить.) Если какие-то две суммы дают одинаковые остатки при делении на $m$‍,‍ то их разность — искомая «алгебраическая» сумма. Если все остатки различны, то они принимают все возможные $m$‍‍ значений 0, 1, $\ldots$‍,‍ $m-1$‍,‍ и сумма, дающая остаток 0, — искомая.

б) Вот пример $s$‍‍ целых чисел таких, что никакая алгебраическая сумма некоторых из них не кратна $m$‍:‍ 1, 2, 4, $\ldots$‍,‍ $2^{s-1}$‍.‍ Действительно, любая такая сумма по модулю не превосходит $1+2+4+\ldots+2^{s-1}\le m-1$‍.‍ С другой стороны, эти суммы не могут быть равны 0: если $2^t$‍‍ — наименьшее слагаемое такой суммы, то вся сумма будет делиться на $2^t$‍,‍ но не будет делиться на $2^{t+1}$‍.‍