|
|
 |
Условие
При дворе короля Артура собрались 2n рыцарей, причём каждый из них имеет
среди присутствующих не более n – 1 врага.
Доказать, что Мерлин, советник Артура, может так рассадить рыцарей за круглым столом, что ни один из них не будет сидеть рядом со своим врагом.
Решение
Условимся называть "друзьями" любых двух рыцарей, не являющихся врагами. Рассадим всех рыцарей за круглым столом произвольно. Пусть где-то за столом сидят рядом рыцарь A и его враг B; для определённости будем считать, что B сидит справа от A.
Мы утверждаем, что за столом найдётся такое место, где рядом сидят рыцари A' – друг A и B' – друг B, причём B' сидит справа от A'. В самом деле, рыцарь A имеет не менее n друзей; мест справа от них также имеется n, а врагов у B не более n – 1 ; значит, хоть одно из мест справа от друга A' рыцаря A занимает друг B' рыцаря B.
Пересадим теперь в обратном порядке всех рыцарей, сидящих справа от A, начиная с рыцаря B и вплоть до рыцаря A'. Ясно, что при этом изменятся лишь две пары соседей: пары A, B и A', B' заменятся на пары друзей A, A' и B, B'. Таким образом, число пар соседей-врагов уменьшится минимум на 1 (оно уменьшится на 2, если A' и B' – враги).
Продолжая пересаживать рыцарей таким же образом и далее, Мерлин может окончательно разъединить за столом все пары сидящих рядом врагов.
