В коллективе n сотрудников. Каждые двое из них либо друзья, либо враги, причём у каждого сотрудника ровно 3 врага. Каждый сотрудник может правдиво заявить: «Враги моих друзей — мои враги». При каких n такое возможно?

задан 21 Сен '19 15:30

10|600 символов нужно символов осталось
1

Если сотрудников 4, и все попарно враждуют, то этот случай подходит: друзей ни у кого нет, и все заявления о них правдивы. Ясно, что n чётно, так как число враждующих пар равно 3n/2. Случай n=6 также подходит -- достаточно рассмотреть полный двудольный граф типа (3,3).

Пусть n>=8. Покажем, что такой случай невозможен. Рассмотрим участника A. У него есть враги B, C, D, а также по крайней мере 4 друга. Пусть E -- один из них. Все враги E, которых имеется 3, входят в состав B, C, D. Значит, это и есть в точности его враги. Поскольку вражда взаимна, и каждый из друзей A может быть взят в качестве E, получаем, что у B более трёх врагов. Противоречие.

ссылка

отвечен 21 Сен '19 18:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×685
×624

задан
21 Сен '19 15:30

показан
268 раз

обновлен
21 Сен '19 18:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru