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