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