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