Задача 67456
|
|
 |
Условие
В Камелот съехались $100$ рыцарей Круглого Стола, любые два из которых либо дружат, либо враждуют (дружба и вражда взаимны). Фея Моргана может выбрать любого рыцаря и сделать так, что он поссорится со всеми своими друзьями и при этом подружится со всеми своими врагами. Накладывать это заклинание Моргана может сколько угодно раз. Докажите, что она сможет добиться того, чтобы в итоге образовались такие две группы по $5$ рыцарей, что каждый рыцарь из первой пятёрки будет враждовать с каждым рыцарем из второй.Решение 1
Возьмём произвольного рыцаря $K_1$. Наложим заклинание на тех рыцарей, кто дружит с $K_1$, тем самым $K_1$ теперь будет со всеми враждовать. Выберем другого рыцаря $K_2$. Помимо их двоих осталось ещё $98$ рыцарей (обозначим их за $\mathcal{T}_1$), поэтому $K_2$ либо дружит хотя бы с $98 / 2 = 49$ рыцарями из $\mathcal{T}_1$, либо враждует хотя бы с $49$ из них. Наложением заклинания на $K_2$ (если необходимо) можно добиться того, чтобы реализовался второй вариант, при этом оно не затронет отношения $K_1$ с рыцарями из $\mathcal{T}_1$. Таким образом, мы добились того, что $K_1$ и $K_2$ вместе враждуют с группой из 49 рыцарей (обозначим их за $\mathcal{T}_2$).Продолжим процесс: выберем третьего рыцаря $K_3$ не из $\mathcal{T}_2$ ($ K_3\ne K_1, K_2$). Тогда в $\mathcal{T}_2$ найдётся либо хотя бы $\lceil 49 / 2\rceil = 25$ врагов $K_3$, либо хотя бы $25$ друзей $K_3$. Во втором случае наложим заклинание на $K_3$, что даст нам группу из $25$ рыцарей (обозначим их за $\mathcal{T}_3$), враждующих с $K_1, K_2, K_3$. Аналогично находятся рыцари $K_4, K_5$ и строятся множества рыцарей $\mathcal{T}_4, \mathcal{T}_5$ размера $\lceil 25 / 2\rceil = 13$ и $\lceil 13 / 2\rceil = 7$ соответственно, при этом все рыцари из $\mathcal{T}_5$ будут враждовать с рыцарями $K_1, \ldots, K_5$, что и требовалось.
Решение 2
Выберем 5 рыцарей, назовём их орденом. На каждого из оставшихся рыцарей наложим заклинание в том и только в том случае, если он дружит не более чем с двумя рыцарями из ордена. После наложения всех заклинаний получим, что каждый рыцарь имеет не менее 3 друзей среди рыцарей ордена. Будем считать двух рыцарей не из ордена схожими, если они дружат с одинаковыми рыцарями ордена. Рыцарей вне ордена 95, а множество возможных друзей может принимать $C_5^3 + C_5^4 + C_5^5 = 10 + 5 + 1 = 16$ различных значений. Значит, по принципу Дирихле найдётся хотя бы $\frac{95}{16} > 5$ схожих рыцарей, назовём их братством. Тогда фея Моргана может наложить заклинания на их общих друзей из ордена, после чего каждый рыцарь из ордена будет враждовать с каждым рыцарем из братства.Решение 3
Нам понадобится следующаяЛемма. $C_k^5 + \smash{C_{99-k}^5} \geqslant \smash{C_{49}^5} + \smash{C_{50}^5}$ для $k \in \mathbb N$ (считаем, что $\smash{C_k^5} = 0$ при $k < 5$).
Доказательство. Достаточно заметить, что для $x < y$ выполнено неравенство $C_x^5 + C_{y}^5 \geqslant C_{x+\smash 1}^5 + C_{y-\smash 1}^5$. Действительно, по условию $y-1 \geqslant x$, поэтому $C_{y-\smash 1}^4 \geqslant C_{x}^4$. По свойству числа сочетаний левая часть равна $\smash{C_{y}^5} - \smash{C_{y-\smash 1}^5}$, а правая равна $C_{x+\smash 1}^5 - C_{x}^5$, что приводит нас к требуемому неравенству. Лемма доказана.
Вернёмся к решению задачи. Назовём метёлкой такую пару из рыцаря (будем называть его королём) и пятёрки других рыцарей (будем называть эту пятерку орденом), что король либо дружит со всеми рыцарями ордена, либо враждует со всеми рыцарями ордена. Ясно, что если рыцарь $K$ дружит с $k$ рыцарями, то метёлок с королём $K$ ровно $\smash{C_k^5} + \smash{C_{99-k}^5}$, что по лемме не меньше $C_{50}^5 + C_{49}^5$, поэтому всего метёлок не менее $100 \cdot (\smash{C_{50}^5} +\smash{C_{49}^5})$. С другой стороны, количество возможных пятёрок равно $C_{100}^5$, поэтому по принципу Дирихле найдётся как минимум $$\frac{100 \cdot (C_{50}^5 + C_{49}^5)}{C_{100}^5} = \frac{100 \cdot 49 \cdot 48 \cdot 47 \cdot 46 \cdot (50 + 45)}{100 \cdot 99 \cdot 98 \cdot 97 \cdot 96} = \frac{47 \cdot 46 \cdot (50 + 45)}{99 \cdot 2 \cdot 97 \cdot 2} > 5$$ метёлок с одним и тем же орденом. Тогда достаточно взять 5 таких метёлок и наложить заклинание на тех королей, которые дружат с рыцарями из ордена. Таким образом, все пять королей будут враждовать со всеми пятью рыцарями этого ордена, что и требовалось.
