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

Проект МЦНМО
при участии
школы 57
Задача 79293
Темы:    [ Принцип крайнего (прочее) ]
[ Принцип Дирихле (прочее) ]
[ Степень вершины ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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


Решение

Возьмём учёного A, число друзей у которого максимально (если таких учёных несколько, возьмём любого из них); обозначим это число через N. Каждый из N друзей учёного A имеет хотя бы одного друга (A), не имеет более N друзей и никакие двое не имеют равного числа друзей. Следовательно, эти люди имеют 1, 2, 3, ..., N друзей. В частности, один из них дружит только с A.

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

олимпиада
Название Московская математическая олимпиада
год
Номер 37
Год 1974
вариант
Класс 10
Тур 2
задача
Номер 4
журнал
Название "Квант"
год
Год 1974
выпуск
Номер 10
Задача
Номер М288

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

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