Задачки

Условие

Среди n рыцарей любые двое – либо друзья, либо враги.
У каждого рыцаря ровно 3 врага, причем враги его друзей – его враги.
Какие значения может принимать n?

Подсказка

Рассмотрите группу из 7 рыцарей

Решение

Ответ: n = 4, 6
Ясно, что n ≥ 4 (рыцарь + 3 врага).
Общее количество пар врагов равно 3·n/2 – целое число.
Следовательно n – четное.
Предположим, что n ≥ 7.
Возьмем следующую группу из 7 рыцарей: рыцарь А; его враг В; остальные два врага рыцаря А; 3 друга рыцаря А.
Тогда получается, что рыцарь В имеет минимум 4 врага (рыцарь А + три друга рыцаря А). Противоречие.
Итак, n < 7.
Получаем n = 4, 6.
n = 4 – все рыцари враги друг другу.
n = 6 – две группы друзей по три рыцаря в каждой