Аддитивная комбинаторика

Если прибавить к каждому элементу некоторое число, то все суммы по элементов будут давать такой же остаток при делении на как раньше. Следовательно, мы можем считать, что наибольшую кратность имеет Пусть — последовательность из ненулевых элементов, — его сумма. Допустим, что условие задачи неверно и Тогда

Докажем, что можно представить в виде суммы не более чем элементов из Распределим элементы по непересекающимся множествам Для этого определим как множество тех элементов которые входят в с кратностью не меньше При этом содержит все различные элементы последовательности. Суммы не более чем по элементов образуют множество По теореме Коши-Дэвенпорта имеем:

Итак, можно представить в виде суммы не более чем элементов из Пусть — последовательность, состоящая из этих не более чем Положим Ясно, что сумма элементов кратна и Если бы оказалось, что то мы бы легко составили подпоследовательность из элементов, кратных добавив к несколько элементов, кратных Следовательно, Применим снова утверждение, доказанное выше, и построим подпоследовательность не более чем из элементов, сумма которой кратна Положим Опять имеем, что сумма элементов равна нулю и Продолжая дальше в том же духе, мы всё-таки сумеем построить последовательность длины c суммой, кратной