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

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

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

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

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

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

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

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

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

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

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

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

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

______________________________________________________________________________________________________________________________________________________

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

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

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

_________________________________________________________________________________________________________________________________________________________________________________

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

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