Комбинаторика на ММО: графы, турниры, логика, конструктивы

Первое решение.

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

Продолжим процесс: выберем третьего рыцаря не из Тогда в найдётся либо хотя бы врагов либо хотя бы 25 друзей Во втором случае наложим заклинание на что даст нам группу из 25 рыцарей, враждующих с (обозначим их за ). Аналогично находятся рыцари и строятся множества рыцарей размера и соответственно, при этом все рыцари из будут враждовать с рыцарями что и требовалось.

Второе решение.

Зафиксируем 5 рыцарей, назовём их орденом. На каждого из оставшихся рыцарей наложим заклинание в том и только в том случае, если он дружит не более чем с двумя рыцарями из ордена. После наложения всех заклинаний получим, что каждый рыцарь имеет не менее 3 друзей среди рыцарей ордена. Будем считать двух рыцарей не из ордена схожими, если они дружат с одинаковыми рыцарями ордена. Рыцарей вне ордена 95, а множество возможных друзей может принимать различных значений. Значит, по принципу Дирихле найдётся хотя бы схожих рыцарей, назовём их братством. Тогда фея Моргана может наложить заклинания на их общих друзей из ордена, после чего каждый рыцарь из ордена будет враждовать с каждым рыцарем из братства.

Третье решение.

Для решения нам понадобится:

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. для (считаем, что при ).

Доказательство. Достаточно заметить, что для натуральных выполнено неравенство Действительно, по условию поэтому По свойству числа сочетаний а что приводит нас к требуемому неравенству. Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

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

метёлок с общим орденом. Тогда достаточно взять 5 таких метёлок и наложить заклинание на тех королей, которые дружат с рыцарями из ордена. Таким образом, все пять королей будут враждовать со всеми пятью рыцарями ордена, что и требовалось.