Отбор ИТМО

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

Оценка.

Пусть у джентльмена с номером () ровно друзей и врагов (). Тогда он отправил ровно писем. Это выражение является квадратным трёхчленом, наибольшее значение которого достигается при и равно Тогда число отправленных всеми джентльменами писем не превосходит

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

Пример.

Покажем, что отправить писем возможно. Достаточно построить “чёрный” подграф: нужно соединить каждого джентльмена с тремя следующими — получим однородный граф степени затем останется соединить каких-то подряд с джентльменами, которые идут на позиций позже по кругу. То есть Тогда степени первых -и вершин станут равны а у -й она останется равной