|
|
 |
Условие
Среди n рыцарей каждые двое – либо друзья, либо враги. У каждого из рыцарей ровно три врага, причём враги его друзей являются его врагами.
При каких n такое возможно?
Решение
Из условия следует, что рыцарей – не менее четырёх. Заметим, что у рыцаря не может быть более двух друзей, иначе найдутся четыре рыцаря, у которых есть общий враг, но тогда у этого врага будет не менее четырёх врагов, что противоречит условию. Значит, у каждого рыцаря не более двух друзей и ровно три врага, следовательно, всего рыцарей – не более шести.
Так как у каждого рыцаря по три врага, то число рыцарей чётно (см. задачу 87972 б).
Примеры. Четыре рыцаря, каждый враждует с остальными тремя.
Шесть рыцарей разбиваем на две тройки: каждый рыцарь дружит с рыцарями из своей тройки и враждует с рыцарями из другой.
Ответ
n = 4 или n = 6.
