|
На конгрессе собрались учёные, среди которых есть друзья. Оказалось, что никакие двое ученых, имеющие на конгрессе равное число друзей, не имеют общих друзей. Докажите, что найдётся учёный, у которого ровно один друг. задан 8 Апр '14 22:52 
student |
|
Условие можно переформулировать так: если у двух учёных есть общий друг, то они имеют разное количество друзей. Рассмотрим учёного A с наибольшим числом друзей, равным $%k$%. При $%k=1$% доказывать нечего. Пусть $%k\ge2$%. Тогда любые два друга учёного A должны иметь разное число друзей, так как они имеют общего друга. Но при этом число друзей у каждого из друзей A находится в пределах от 1 до $%k$%: число друзей здесь не может быть нулевым, и не может превышать $%k$%. Поскольку числа не повторяются, то каждое из значений принимается по разу, и тогда найдётся учёный, у кого в друзьях только один A. отвечен 9 Апр '14 5:00 
falcao |