Двойной подсчёт
Ошибка.
Попробуйте повторить позже
В думе 
депутатов образовали 
фракций по 
человек в каждой. Докажите, что найдутся 
депутата, состоящие вместе хотя
бы в двух фракциях.
Подсказка 1
Обозначим n=16000. Предположим, что каждые две фракции имеют не более трёх общих членов. Пусть двое секретарей A и B составляют списки всевозможных председателей на три заседания Думы. A считает, что любой депутат может быть председателем на каждом из этих заседаний. Какое количество списков он получит?
Подсказка 2
Правильно, 1600³! B считает, что на каждом заседании могут председательствовать только члены одной(не важно, какой именно) фракции, поэтому сначала он запросил соответствующие списки от каждой фракции. Сколько B получит списков?
Подсказка 3
Верно! B получил получил 80³ ⋅n списков. После этого B выбросил из списков, поданных i-ой фракцией, те тройки, которые уже вошли в списки одной из предыдущих i− 1 фракций. Сколько максимум B выбросил списков?
Подсказка 4
Точно! Так как каждые две фракции(а таких пар n(n-1)/2) выдвинули всех своих общих членов, то B при формировании своих списков выбросил не более, чем n(n-1)/2 * 3³ списков. Осталось заметить, что A точно составил не меньше списков, чем B, и записать это неравенство, получить противоречие.
Обозначим 
Предположим, что каждые две фракции имеют не более трёх общих членов.
Пусть двое секретарей 
и 
составляют списки всевозможных председателей на три заседания Думы. 
считает, что любой депутат
может быть председателем на каждом из этих заседаний, поэтому у него получилось 
списков. 
считает, что на каждом заседании
могут председательствовать только члены одной (не важно, какой именно) фракции, поэтому сначала он запросил соответствующие
списки от каждой фракции и получил 
списков. После этого 
выбросил из списков, поданных 
-ой фракцией,
те тройки, которые уже вошли в списки одной из предыдущих 
фракций. Так как каждые две фракции (а таких
пар 
) выдвинули всех своих общих членов, то 
при формировании своих списков выбросил не более, чем 
списков.
Очевидно, что списков, которые составил 
не меньше, чем списков, которые составил 
то есть
Противоречие.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
