Задача
COM-B1-M05-P022 Пять знакомых или незнакомых относительно одного
#22
★★★★☆ Уровень 4 из 5
В компании из \(10\) человек докажите, что найдётся человек, у которого есть либо \(5\) знакомых, либо \(5\) незнакомых.
Возьмите любого человека и рассмотрите остальных \(9\).
Выберем произвольного человека \(A\). Среди остальных \(9\) каждый либо знаком с \(A\), либо не знаком. Два ящика: знакомые и незнакомые. По усиленному принципу Дирихле в одном из них не менее \(\lceil9/2 ceil=5\) человек. Значит у \(A\) есть \(5\) знакомых или \(5\) незнакомых.
Подготовка к Ramsey-рассуждениям.