Аддитивная комбинаторика
Ошибка.
Попробуйте повторить позже
Пусть 
— простое число и 
Рассмотрим множество из 
целых чисел. Докажите, что если сумма никаких 
чисел из
этого множества не делится на 
то какой-то остаток по модулю 
встречается в этом множестве не менее чем 
раз.
Подсказка 1
Добавление ко всем элементам множества по k не меняет задачи, так что можно считать, что чаще всего встречаются нули и их h. Решая от противного, предположим, что h≤p-k. Тогда оставшихся элементов хотя бы p, а их сумма s. Можно доказать, что можно выбрать не более h элементов так, что их сумма сравнима с s по модулю p.
Подсказка 2
Для этого разобьём элементы на множества из различных чисел по кратности (в первом все элементы, во втором — те, кто встречаются хотя бы дважды и так далее). Во все множества, кроме первого, добавим 0. Тогда их суммы представляют из себя суммы не более чем h элементов, причём по теореме Коши-Дэвенпорта мощность такой суммы будет p.
Подсказка 3
Давайте выкинем элементы, которые в сумме дают s. Тогда оставшиеся элементы в сумме делятся на p, причём их осталось хотя бы p-h. Тогда их осталось больше, чем p. Мы получили меньшее по размеру множество, аналогичное предыдущему.
Если прибавить к каждому элементу некоторое число, то все суммы по 
элементов будут давать такой же остаток при
делении на 
как раньше. Следовательно, мы можем считать, что наибольшую кратность 
имеет 
Пусть 
—
последовательность из ненулевых элементов, 
— его сумма. Допустим, что условие задачи неверно и 
Тогда
Докажем, что 
можно представить в виде суммы не более чем 
элементов из 
Распределим элементы 
по 
непересекающимся множествам 
Для этого определим 
как множество тех элементов 
которые входят в 
с
кратностью не меньше 
При этом 
содержит все различные элементы последовательности. Суммы не более чем по 
элементов
образуют множество 
По теореме Коши-Дэвенпорта имеем:
Итак, 
можно представить в виде суммы не более чем 
элементов из 
Пусть 
— последовательность, состоящая из этих не
более чем 
Положим 
Ясно, что сумма элементов 
кратна 
и 
Если бы оказалось, что 
то
мы бы легко составили подпоследовательность из 
элементов, кратных 
добавив к 
несколько элементов, кратных 
Следовательно, 
Применим снова утверждение, доказанное выше, и построим подпоследовательность 
не более чем из
элементов, сумма которой кратна 
Положим 
Опять имеем, что сумма элементов 
равна нулю и
Продолжая дальше в том же духе, мы всё-таки сумеем построить последовательность длины 
c суммой, кратной
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
