Задача
COM-B1-M09-P013 Два человека с одинаковым числом знакомых
#13
★★★☆☆ Уровень 3 из 5
Докажите, что в любой компании из \(2n\) человек найдутся двое с одинаковым числом знакомых внутри компании.
Возможные степени от \(0\) до \(2n-1\), но \(0\) и \(2n-1\) не могут встречаться вместе.
Степени могут быть числами \(0,1,\ldots,2n-1\). Однако степени \(0\) и \(2n-1\) не могут встречаться одновременно: если кто-то знаком со всеми, то никто не имеет \(0\) знакомых. Поэтому реально доступно не более \(2n-1\) разных значений степеней. Людей \(2n\), значит по принципу Дирихле у двух степени совпадают.
Стандартная олимпиадная задача на графы и Дирихле.