Тема ИТМО (открытка)

Отбор ИТМО

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела итмо (открытка)

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 1#36854

В городе Джентльвилле живут $15$ джентльменов, любые двое из которых либо дружат, либо враждуют. В какой-то момент каждый джентльмен попросил каждого из своих друзей послать открытку ненависти каждому из своих врагов (джентльмен $A$ просит джентльмена $B$ послать открытку всем врагам джентльмена $B$ ). Каждый из джентльменов выполнил все просьбы; при этом он посылал каждому из своих врагов такое количество открыток, сколько раз его об этом просили. Какое наибольшее количество открыток могло быть послано?

Источники: ИТМО-2016, отборочный тур, 11 класс (см. olymp.itmo.ru)

Подсказки к задаче

Подсказка 1!

1) Так, было бы здорово оценить количество открыток как-то, в зависимости от количества друзей, чтобы попробовать посчитать максимум..... Например, если у человека друзей будет х, а врагов соответственно 14-х, то сколько открыток он пошлет?

Подсказка 2!

2) Так, хорошо, х(14-х)! Нужно понять, где это выражение принимает максимум, и проверить, получится ли наш максимум достигнуть... Было тут у нас какое-то утверждение про степени вершин в графе... Хм...

Подсказка 3!

3) Ага, вот оно! Лемма о рукопожатиях! Теперь идейно задачу решили, осталось только немного разобраться, как все же получить новый максимум!

Показать ответ и решение

Рассмотрим полный граф на $15$ вершинах, вершинами которого являются джентльмены, а рёбрами — отношения между ними. Покрасим между двумя вершинами в белый цвет, если джентльмены, соответствующие этим вершинам дружат. А чёрные ребра будут символизировать вражду между людьми.

Оценка.

Пусть у джентльмена с номером $n$ ( $1≤ n≤ 15$ ) ровно $xn$ друзей и $14 − xn$ врагов ( $xn ∈ ℕ∪ {0}$ ). Тогда он отправил ровно $xn⋅(14− xn)$ писем. Это выражение является квадратным трёхчленом, наибольшее значение которого достигается при $xn =7$ и равно $49.$ Тогда число отправленных всеми джентльменами писем не превосходит $49 ⋅15.$

Покажем, что отправить ровно $49⋅15$ писем невозможно по лемме о рукопожатиях (в любом графе количество вершин нечётной степени чётно). Действительно, в таком случае у каждого джентльмена должно быть $7$ друзей и $7$ врагов. Рассмотрим подграф из всех вершин и только белых рёбер. В этом подграфе количество рёбер (количество пар друзей среди джентльменов) равно половине от суммы степеней вершин (у каждого по $7$ друзей, но одну и ту же пару считаем дважды), то есть $7⋅125.$ Противоречие с тем, что это число должно быть целым.

Пример.

Покажем, что отправить $49 ⋅15− 1= 734$ писем возможно. Достаточно построить “чёрный” подграф: нужно соединить каждого джентльмена с тремя следующими — получим однородный граф степени $6,$ затем останется соединить каких-то $7$ подряд с джентльменами, которые идут на $7$ позиций позже по кругу. То есть $1 ⇐ ⇒ 8,2 ⇐⇒ 9...7 ⇐⇒ 14.$ Тогда степени первых $14$ -и вершин станут равны $7,$ а у $15$ -й она останется равной $6.$