Аддитивная комбинаторика
Ошибка.
Попробуйте повторить позже
Пусть 
— множество из 
чисел, причем оно содержит ровно 
различных по модулю 
Докажите, что в 
найдется
подмножество с суммой, делящейся на 
Подсказка 1
Конечно, задачу нужно решать от противного. Будем полагать, что никакая подпоследовательность данной последовательности чисел не дает 0 в остатке. Попробуем посмотреть на суммы, которые можно составить из первых m членов последовательности. От каких суммы они наверняка отличаются?
Подсказка 2
Верно! Они точно отличаются от всех 502-m сумм последних r элементов, где r не меньше m+1. Попробуем теперь выбрать m с хорошим свойством: так, чтобы можно было гарантировать, что первые m членов будут определять достаточно большое количество различных сумм. Какое число сумм, зависящее от m, можно наверняка гарантировать?
Подсказка 3
Докажем, что можно гарантировать не менее m+39 сумм! Как это можно показать?
Подсказка 4
Всего в последовательности только 10 различных элементов, а потому есть и ненулевой элемент, входящий не менее 51 раза (если бы он был нулевым, то задача не имела бы смысла). Можно ли теперь сделать так, чтобы работать не с абстрактным элементом a, встречающимся 51 раз, а с более конкретным?
Подсказка 5
Конечно! Очевидное сведение к случаю a = 1 состоит в том, что можно разделить на обратный элемент к ненулевому a все числа последовательности. Тогда остальные числа можно считать просто какими-то числами от 1 до 540 (поскольку нас интересуют только ненулевые остатки по модулю 541). Попробуем теперь рассмотреть два случая: найдется число большее 51 и все числа не превосходят 51. Что можно сказать о наборе во втором случае?
Подсказка 6
Точно! В виде сумм наших чисел представимы все натуральные числа от 1 до суммы всех чисел. Однако самая большая из таких сумм не меньше суммы первых 10 натуральных чисел и 492. Тогда вся сумма больше 541, что невозможно! Перейдем к первому случаю. Каким ограничениям удовлетворяет число, большее 51?
Подсказка 7
Верно! Оно точно меньше 488, ведь у нас в запасе есть 51 единица (после деления на a в множестве остатков по модулю 541). Какое теперь можно выбрать m, чтобы получить не менее m+39 различных сумм первых m членов?
Подсказка 8
Точно! Положим m = 52. Тогда у нас на самом деле есть не менее 103 различных сумм. Решена ли теперь задача?
Число 
будем для ясности обозначать через 
а 
— через 
Пусть 
— данная последовательность. Допустим,
что никакая её подпоследовательность не даёт в сумме 
Пусть 
— некоторое число. Заметим, что тогда все суммы, которые
можно получить, выбирая слагаемые только из 
первых членов последовательности, отличны от всех 
сумм вида 
где
(иначе вычтем одну сумму из другой — останется как раз подпоследовательность c суммой, кратной 
Покажем,
что можно выбрать 
так, что первые 
членов последовательности будут определять не менее 
различных
сумм.
Так как в последовательности встречается всего 
различных элементов, какой-то элемент 
входит в неё не менее 
раза. Так как 
— простое число, в 
возможно деление (засчёт взятия обратного остатка), значит, мы можем
поделить все элементы последовательности на 
результат каждого деления можно интерпретировать как число от 
до
Таким образом, мы можем считать, что 
а остальные элементы последовательности — какие-то натуральные
числа от 
до 
Если ни одно из чисел 
не превосходит 
то в виде сумм чисел 
представимы все натуральные числа от 
до
последняя сумма никак не меньше чем сумма первых 
натуральных чисел плюс 
Все вместе — больше 
Противоречие.
Если же в последовательности имеется число, большее 
мы можем считать, что 
(При этом 
так как иначе при помощи 
и нескольких единиц можно сразу получить подпоследовательность с суммой, кратной
) Полагая 
мы видим, что первые 
членов последовательности представляют не менее 
сумм, что и
требовалось.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
