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

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

Чтобы воплотить этот план в жизнь, нам осталось доказать следующее утверждение.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть даны подпоследовательности исходной последовательности длины каждая из которых содержит не меньше и не больше элементов. Тогда мы можем так перенумеровать элементы последовательности что ни одно из множеств в новой нумерации не будет интервалом.

Доказательство. Когда нам не важен порядок элементов, мы будем в этом доказательстве наряду со словом “последовательность” использовать слово “множество”.

Индукция по Базу при нетрудно получить хотя бы перебором.

Пусть утверждение доказано для какого-то значения Докажем его для т. е. проверим, что верно следующее утверждение.

Дана последовательность И пусть — несколько её подпоследовательностей, причём и подпоследовательности содержат от до элементов. Тогда существует перенумерация, в которой ни одна из подпоследовательностей не является интервалом.

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

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