Задача 109750
|
|
 |
Условие
В компании из 2n + 1 человека для любых n человек найдётся отличный от них человек, знакомый с каждым из них.
Докажите, что в этой компании есть человек, знающий всех.
Решение
Очевидно, что есть двое знакомых, и если есть k попарно знакомых (где k ≤ n), то по условию найдётся отличный от них человек, знакомый со всеми этими k людьми. Отсюда следует, что найдутся n + 1 попарно знакомых: A1, ..., An+1. Рассмотрим остальных n человек. По условию существует отличный от них человек Ai, знающий их всех. Но тогда Ai знаком со всеми.
