МОШ 2025, 10 класс, задача 3
В Камелот съехались рыцарей Круглого Стола, любые два из которых либо дружат, либо враждуют (дружба и вражда взаимны). Фея Моргана может выбрать любого рыцаря и сделать так, что он поссорится со всеми своими друзьями и при этом подружится со всеми своими врагами. Накладывать это заклинание Моргана может сколько угодно раз. Докажите, что она сможет добиться того, чтобы в итоге образовались такие две группы по рыцарей, что каждый рыцарь из первой пятёрки будет враждовать с каждым рыцарем из второй.
(М. Федотова, И. Богданов)
Решение 1. Возьмём произвольного рыцаря . Наложим заклинание на тех рыцарей, кто дружит с , тем самым теперь будет со всеми враждовать. Выберем другого рыцаря . Помимо их двоих осталось ещё рыцарей (обозначим их за ), поэтому либо дружит хотя бы с рыцарями из , либо враждует хотя бы с из них. Наложением заклинания на (если необходимо) можно добиться того, чтобы реализовался второй вариант, при этом оно не затронет отношения с рыцарями из . Таким образом мы добились того, что и вместе враждуют с группой из рыцарей (обозначим их за ).
Продолжим процесс: выберем третьего рыцаря не из . Тогда в найдётся либо хотя бы врагов , либо хотя бы друзей . Во втором случае наложим заклинание на , что даст нам группу из рыцарей, враждующих с (обозначим их за ). Аналогично находятся рыцари , и строятся множества рыцарей , размера и соответственно, при этом все рыцари из будут враждовать с рыцарями , что и требовалось.
Решение 2. Зафиксируем рыцарей, назовём их орденом. На каждого из оставшихся рыцарей наложим заклинание в том и только в том случае, если он дружит не более чем с двумя рыцарями из ордена. После наложения всех заклинаний получим, что каждый рыцарь имеет не менее друзей среди рыцарей ордена. Будем считать двух рыцарей не из ордена схожими, если они дружат с одинаковыми рыцарями ордена. Рыцарей вне ордена , а множество возможных друзей может принимать
различных значений. Значит, по принципу Дирихле найдётся хотя бы схожих рыцарей, назовём их братством. Тогда фея Моргана может наложить заклинания на их общих друзей из ордена, после чего каждый рыцарь из ордена будет враждовать с каждым рыцарем из братства.
Решение 3. Для решения нам понадобится следующая
Лемма. для (считаем, что при ).
Доказательство. Достаточно заметить, что для натуральных выполнено неравенство
Действительно, по условию , поэтому . По свойству числа сочетаний левая часть равна , а правая равна , что приводит нас к требуемому неравенству. Лемма доказана.
Вернёмся к решению задачи. Назовём метёлкой пару из рыцаря (будем называть его королём) и пятёрки других рыцарей (будем называть их орденом), для которой король одновременно дружит или враждует со всеми рыцарями из ордена. Ясно, что если рыцарь дружит с рыцарями, то метёлок с королём ровно , что по лемме не меньше , поэтому всего метёлок не менее . С другой стороны, количество возможных пятёрок равно , поэтому по принципу Дирихле найдётся как минимум
метёлок с общим орденом. Тогда достаточно взять таких метёлок и наложить заклинание на тех королей, которые дружат с рыцарями из ордена. Таким образом, все пять королей будут враждовать со всеми пятью рыцарями ордена, что и требовалось.