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

Число будем для ясности обозначать через а — через Пусть — данная последовательность. Допустим, что никакая её подпоследовательность не даёт в сумме Пусть — некоторое число. Заметим, что тогда все суммы, которые можно получить, выбирая слагаемые только из первых членов последовательности, отличны от всех сумм вида где (иначе вычтем одну сумму из другой — останется как раз подпоследовательность c суммой, кратной Покажем, что можно выбрать так, что первые членов последовательности будут определять не менее различных сумм.

Так как в последовательности встречается всего различных элементов, какой-то элемент входит в неё не менее раза. Так как — простое число, в возможно деление (засчёт взятия обратного остатка), значит, мы можем поделить все элементы последовательности на результат каждого деления можно интерпретировать как число от до

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

Если же в последовательности имеется число, большее мы можем считать, что (При этом так как иначе при помощи и нескольких единиц можно сразу получить подпоследовательность с суммой, кратной ) Полагая мы видим, что первые членов последовательности представляют не менее сумм, что и требовалось.