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