Problem
COM-B1-M11-P016 Same Number of Acquaintances
#16
★★★☆☆ Level 3 of 5
Prove that in any group of \(10\) people, two people have the same number of acquaintances within the group.
Degrees \(0\) and \(9\) cannot occur together.
Possible acquaintance numbers are from \(0\) to \(9\). But \(0\) and \(9\) cannot occur together: if someone knows everyone, nobody has \(0\) acquaintances. Thus there are at most \(9\) different possible values, but \(10\) people. By pigeonhole, two degrees are equal.
Graph idea without the formal word “graph” in the statement.