В компании из 100 человек любые десять человек имеют общего знакомого среди остальных. Докажите, что любые пять человек из этой компании имеют не менее шести общих знакомых среди остальных.
Подсказка
Предположим, что нашлись пять человек, которые имеют не более пяти общих знакомых. Рассмотрим десятку, содержащую этих пятерых человек и всех их общих знакомых.
Решение
Предположим, что нашлись пять человек, которые имеют не более пяти общих знакомых. Рассмотрим десятку, содержащую этих пятерых человек и всех их общих знакомых. По условию выбранные 10 человек имеют общего знакомого, но тогда мы нашли ещё одного общего знакомого для пятерых человек. Противоречие.