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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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