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