0
2

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

задан 8 Апр '14 22:52

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

Условие можно переформулировать так: если у двух учёных есть общий друг, то они имеют разное количество друзей.

Рассмотрим учёного A с наибольшим числом друзей, равным $%k$%. При $%k=1$% доказывать нечего. Пусть $%k\ge2$%. Тогда любые два друга учёного A должны иметь разное число друзей, так как они имеют общего друга. Но при этом число друзей у каждого из друзей A находится в пределах от 1 до $%k$%: число друзей здесь не может быть нулевым, и не может превышать $%k$%. Поскольку числа не повторяются, то каждое из значений принимается по разу, и тогда найдётся учёный, у кого в друзьях только один A.

ссылка

отвечен 9 Апр '14 5:00

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

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

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

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

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

отмечен:

×59

задан
8 Апр '14 22:52

показан
1698 раз

обновлен
9 Апр '14 5:00

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

по почте:

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

по RSS:

Ответы

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

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