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

Заметим, что на обратных сторонах карточек встречается возрастающая по включению последовательность из множеств:

Если разложим карточки на две кучи: в одной куче карточки, на лицевой стороне которых выписаны множества с четным числом элементов, а в другой — с нечетным. Тогда в каждой из куч величина «число элементов множества на лицевой стороне карточки» принимает лишь различных значений, поэтому ни в одной из куч на лицевых сторонах карточек не найдётся согласованная с последовательностью () возрастающая цепочка из множества. И даже более цинично: расслоим карточки на 2n слов по числу элементов, после чего слоев целиком помещаем в одну кучу, а другие слоев в другую. Ни одна из куч не содержит цепь длины

Докажем индукцией по что среди сумм всевозможных подпоследовательностей есть хотя бы различных остатков по модулю Для это очевидно, так как даёт один остаток.

Пусть утверждение верно для чисел (), добавим к ним Пусть до этого среди сумм подпоследовательностей встречались различные остатки Рассмотрим остатки Ясно, что они различные. Предположим, что это просто перестановка остатков Тогда получаем, что Получается, что кратно Однако а значит что противоречит условию. Следовательно, среди чисел есть новый остаток. Переход доказан.

Тогда среди сумм всевозможных подпоследовательностей чисел есть любой остаток по модулю что и требовалось.

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

Следовательно, (множество вычетов по модулю ), откуда и следует требуемое утверждение.

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

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

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

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

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

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

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

Докажем индукцией по , что среди сумм всевозможных подпоследовательностей есть хотя бы различных остатков по модулю Для это очевидно, так как даёт один остаток.

Пусть утверждение верно для чисел (), добавим к ним Пусть до этого среди сумм подпоследовательностей встречались различные остатки Рассмотрим остатки Ясно, что они различные. Предположим, что это просто перестановка остатков Тогда получаем, что Получается, что кратно Однако а значит что противоречит условию. Следовательно, среди чисел есть новый остаток. Переход доказан.

Тогда среди сумм всевозможных подпоследовательностей чисел есть любой остаток по модулю что и требовалось.

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим всевозможные суммы нескольких из выписанных чисел. Количество таких сумм будет равно (мы учитываем пустую сумму). Согласно принципу Дирихле некоторые две из этих сумм и дают одинаковый остаток при делении на Разность этих сумм делится на и представляет собой сумму нескольких данных чисел со знаками или

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

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

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

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

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

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

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

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

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

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

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