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