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