2019-04-29
При дворе короля Артура собрались $2n$ рыцарей, причем каждый из них имеет среди присутствующих не более $n - 1$ врагов. Доказать, что Мерлин - советник Артура - может так рассадить рыцарей за круглым столом, что ни один из них не будет сидеть рядом со своим врагом.
Решение:
Условимся называть «друзьями» любых двух рыцарей, не являющихся врагами; далее, начнем с того, что рассадим всех рыцарей за круглым столом произвольно. Пусть где-то за столом сидят рядом рыцарь $A$ и его враг $B$; для определенности будем считать, что $B$ сидит справа от $A$. Мы утверждаем, что за столом найдется такое место, где рядом сидят рыцари $A^{ \prime}$ - друг $A$ и $B^{ \prime}$ - друг $B$, причем $B^{ \prime}$ сидит справа от $A^{ \prime}$ (см. рис. а). В самом деле, рыцарь $A$ имеет не менее $n$ друзей; мест справа от них также имеется $k$, а врагов у $B$ не более $n - 1$ - значит, хоть одно из мест справа от друга $A$ рыцаря $A$ занимает друг $B^{ \prime}$ рыцаря $B$. Пересадим теперь в обратном порядке всех рыцарей, сидящих справа от $A$, начиная с рыцаря $B$ и вплоть до рыцаря $A^{ \prime}$ (рис. б). Ясно, что при этом изменятся лишь пары $A, B$ и $A^{ \prime}, B^{ \prime}$ соседей - они заменятся на пары друзей $A, A^{ \prime}$ и $B, B^{ \prime}$. Таким образом, число пар сидящих рядом врагов уменьшится минимум на 1 (оно уменьшится даже на 2, если рыцари $A^{ \prime}$ и $B^{ \prime}$ - враги). Продолжая пересаживать рыцарей таким же образом и далее, Мерлин может окончательно разъединить за столом все пары сидящих рядом врагов.
Ответ: Пусть $A$ и $B$ - два рядом сидящих врага; докажите, что Мерлин может пересадить часть рыцарей так, чтобы пара сидящих рядом врагов заменилась парой $A, A^{ \prime}$ сидящих рядом друзей, а ни одна пара соседей-друзей не заменилась парой врагов.