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

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

т.е. не принадлежит или не принадлежит следовательно, количество элементов не превосходит числа количество пар, чем получено противоречие.

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

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

Предложение 1. Пусть дано целое число и тогда

Доказательство. Существует биекция между множествами и которая каждому остатку первого множества ставит в соответствие остаток второго.

Предложение 2. Пусть — множества вычетов, причем Тогда существует целое число для которого

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

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

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

Предложение 3. Если то

Доказательство. Достаточно показать, что произвольный элемент множества лежит в Элемент представим в виде суммы где без ограничений общности можем считать, что но тогда и вычет

______________________________________________________________________________________________________________________________________________________

Вернемся к доказательству задачи. Из множества пар множеств выберем такую, что мощность множества меньшей мощности минимальна по всем парам. Без ограничений общности, но тогда, в силу предложения существует целое при котором

Тогда, по предложению и предложению поскольку множество непусто,

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

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Утверждение задачи суть теорема Коши-Дэвенпорта. Известно следующее утверждение, в доказательстве которого она полезна.

Утверждение. Сравнение по простому модулю имеет решение для любого

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

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

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

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

Ясно, что они различные. Предположим, что это просто перестановка остатков Тогда получаем, что

Получается, что кратно Однако а значит, что противоречит условию. Следовательно, среди чисел

есть новый остаток. Переход доказан.

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

Заметим, что если какой-то остаток встречается раз, то мы можем взять этот остаток раз и условие будет выполнятся. Будем считать, что каждый остаток встречается меньше раз. Давайте положим в множество элементы Теперь будем последовательно заполнять множества оставшимися остатками. А именно, будем брать остаток и последовательно его класть в множества и так для каждого остатка. Заметим, что два раза мы в одно множество один и тот же остаток положить не можем, так как тогда этого остатка было бы хотя бы штук. Также заметим, что пустых множеств не будет, ведь у нас остался хотя бы элемент (в силу того, что Тогда по теореме Коши-Дэвенпорта получаем, что

Что и требовалось.

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

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

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

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

Случаи разбираются вручную. Пусть есть элементы Для любого другого элемента рассмотрим суммы и

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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

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

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

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

Переформулируем задачу. Будем считать, что у нас номиналы копеек это соответственные остатки по модулю и нам нужно выбрать остатков сумма которых делится на Заметим, что монет не хватит так, как нам могут выпасть монет с остатком и монет с остатком Докажем, что для любого натурального нам достаточно вытащить монету, чтоб можно было выбрать монет с суммой, которая делится на Индукцией по количеству простых множителей числа

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

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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

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

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

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

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

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