ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 64490
Темы:    [ Степень вершины ]
[ Примеры и контрпримеры. Конструкции ]
[ Четность и нечетность ]
Сложность: 4-
Классы: 9,10,11
В корзину
Прислать комментарий

Условие

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


Решение

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


Ответ

n = 4  или  n = 6.

Источники и прецеденты использования

олимпиада
Название Московская математическая регата
год
Год 2013/14
класс
Класс 11
задача
Номер 11.4.3

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .