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

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

Тогда так как в противном случае, дополнив нескольким нулями, мы получили бы подпоследовательность из элементов с суммой, кратной Итак, в последовательности не меньше элементов. Возьмем любые из них, пусть они образуют последовательность Пусть — наибольшая кратность элемента в Тогда по определению числа Разобьем каноническим образом в объединение непересекающихся множеств (не последовательностей!) и положим Заметим теперь, что не принадлежит и что при никакие элементов не дают в сумме Действительно, так как то если бы какие-то элементов из давали бы в сумме мы могли бы объединить эти элементы с и получили бы более длинную подпоследовательность с суммой, кратной что противоречит определению Таким образом, мы проверили, что к набору можно последовательно применять теорему Кемпермана-Шерка (подробнее про эту теорему см. ниже), что даёт нам неравенство

Иными словами, если к последовательности добавить нулей из то полученная последовательность имеет не меньше различных сумм из элементов, кратных Добавив оставшиеся элементы (а их в точности ) к каждой из этих сумм, мы получим различных сумм из элементов, кратных

Теорема Кемпермана — Шерка. Пусть  — натуральное число, и  — два подмножества содержащие и пусть уравнение где имеет относительно и единственное решение Тогда

Доказательство. Можно считать, что Среди всех пар противоречащих утверждению задачи, выберем такую, в которой величина наименьшая. Заметим, что существует элемент из B, такой что не является подмножеством Действительно, если бы это было не так, то для ненулевого элемента из мы бы имели равенство и, в частности, так как лежит в мы бы нашли нетривиальное представление что противоречит условию. Воспользуемся элементом чтобы перестроить имеющуюся пару множеств. А именно, пусть — это множество всех таких из для которых не лежит в Положим

Ясно, что не лежит в поэтому по-прежнему лежит в Очевидно, лежит в

Уравнение для множеств имеет только тривиальное решение. Действительно, если нашлось нетривиальное решение где лежит в лежит в то тогда и что невозможно, так как лежит в лежит в а нетривиальных разложений нуля для множеств и не существует.

Наконец, отметим, что

Итак, мы построили новую пару множеств противоречащую утверждению задачи, но при этом Противоречие.