Question

В компании, состоящей из 2n+1 человека, для любого n человек требуется один человек, знакомый с каждым из них.Докажите, что в этой компании есть человек, который знает все​

Answer 1

Ответ:

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