Problem
COM-B1-M09-P013 Two People with the Same Number of Acquaintances
#13
★★★☆☆ Level 3 of 5
Prove that in any group of \(2n\) people, two people have the same number of acquaintances within the group.
Possible degrees are from \(0\) to \(2n-1\), but \(0\) and \(2n-1\) cannot both occur.
Degrees can be \(0,1,\ldots,2n-1\). However, degrees \(0\) and \(2n-1\) cannot occur together: if someone knows everyone, then nobody has \(0\) acquaintances. Thus at most \(2n-1\) different degree values are available. There are \(2n\) people, so by the pigeonhole principle two degrees are equal.
Standard olympiad problem combining graphs and pigeonhole.