Название: Враг моего друга...
Отправлено: fortpost от Февраль 10, 2013, 23:51:33
Среди n рыцарей каждые двое — либо друзья, либо враги. У каждого рыцаря ровно три врага, причём враги его друзей являются его врагами. При каких n такое возможно?
Название: Re: Враг моего друга...
Отправлено: RaiN от Февраль 11, 2013, 09:58:27
Показать скрытый текст
n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.
Название: Re: Враг моего друга...
Отправлено: fortpost от Февраль 11, 2013, 10:11:29
Показать скрытый текст
n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.
RaiN - Браво! :beer: Но еще одно решение есть.
Название: Re: Враг моего друга...
Отправлено: RaiN от Февраль 11, 2013, 10:49:13
Показать скрытый текст
n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.
RaiN - Браво! :beer: Но еще одно решение есть. Еще одно решение, или еще одно возможное n?
Название: Re: Враг моего друга...
Отправлено: fortpost от Февраль 11, 2013, 10:53:20
Показать скрытый текст
n=4, все враги.
Доказательство от противного:
Рассмотрим задачу в виде графа. Каждая вершина - рыцать. Если между двумя вершинами есть ребро - они друзья. Нет - враги. У каждого рыцаря 3 врага, а значит (n-4) друзей. (n-4)>0.
Пусть одна вершина - Вася. Проведем для него эти (n-4) ребер. Если хоть какие-то двое из этих друзей не соединены между собой - то они враги. Получается, что враг друга Васи - друг Васи. Этого быть не может. Значит друзья - полный граф.
Остаются отдельные 3 вершины, не связанные с остальными. Ни от кого из них (n-4) ребер провести нельзя, значит при n>4 задача не решается.
Для n<4 не найдется 3-х врагов.
RaiN - Браво! :beer: Но еще одно решение есть. Еще одно решение, или еще одно возможное n? Еще одно возможное n.
Название: Re: Враг моего друга...
Отправлено: Tim от Февраль 11, 2013, 11:00:50
Название: Re: Враг моего друга...
Отправлено: fortpost от Февраль 11, 2013, 11:07:39
|