Олимпиадная задача по теории графов: друзья на конгрессе (Конягин С. В
На конгресс собрались учёные, среди которых есть друзья. Оказалось, что каждые два из них, имеющие на конгрессе равное число друзей, не имеют общих друзей. Доказать, что найдётся учёный, который имеет ровно одного друга из числа участников конгресса.
Разобрать решение
Возьмём учёного A, число друзей у которого максимально (если таких учёных несколько, возьмём любого из них); обозначим это число через N. Каждый из N друзей учёного A имеет хотя бы одного друга (A), не имеет более N друзей и никакие двое не имеют равного числа друзей. Следовательно, эти люди имеют 1, 2, 3, ..., N друзей. В частности, один из них дружит только с A.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.