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