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