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