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

Проект МЦНМО
при участии
школы 57
Задача 31070
Темы:    [ Степень вершины ]
[ Разбиения на пары и группы; биекции ]
[ Четность и нечетность ]
Сложность: 3+
Классы: 6,7,8
В корзину
Прислать комментарий

Условие

В кружке у каждого члена имеется один друг и один враг. Доказать, что
  а) число членов чётно.
  б) кружок можно разделить на два нейтральных кружка.


Решение

  а) Весь кружок разбивается на пары друзей.

  б) Поскольку степень каждой вершины соответствующего графа равна 2, то он разбивается на циклы. В каждом цикле рёбра "дружбы" и "вражды" чередуются, значит, тех и других поровну. Поместив в один кружок членов каждого цикла, взятых через одного, мы получим кружок, где нет ни друзей, ни врагов. Оставшиеся члены образуют второй нейтральный кружок.

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

книга
Автор Иванов С.В.
Название Математический кружок
глава
Номер 5
Название Графы
Тема Теория графов
задача
Номер 02

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

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