Враг моего друга...

[fortpost]

Среди n рыцарей каждые двое — либо друзья, либо враги. У каждого рыцаря ровно три врага, причём враги его друзей являются его врагами. При каких n такое возможно?

[RaiN]

Показать скрытый текст

n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.

[fortpost]

Показать скрытый текст

n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.

RaiN - Браво!
Но еще одно решение есть.

[RaiN]

Показать скрытый текст

n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.

RaiN - Браво!
Но еще одно решение есть.

Еще одно решение, или еще одно возможное n?

[fortpost]

Показать скрытый текст

n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.

RaiN - Браво!
Но еще одно решение есть.

Еще одно решение, или еще одно возможное n?

Еще одно возможное n.

[Tim]

Показать скрытый текст

6

[fortpost]

Показать скрытый текст

6

Ага, это!