Решение задачи 425

Условие:

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

Решение:

Рассмотрим ученого, у которого большего всего друзей (если таких несколько, возьмем любого). Пусть это ученый А и пусть у него N друзей. Заметим, что среди этих N друзей у любых двух есть общий друг — ученый А, значит по условию задачи у всех этих N ученых разное число друзей. Также каждый из N друзей ученого А имеет хотя бы одного друга (ученый А) и не более N друзей. Значит, у этих людей 1, 2, ..., N друзей. То есть найдется ученый, у которого только один друг (дружит только с ученым А).