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