Problem
COM-B1-M05-P007 Same Number of Acquaintances
#7
★★☆☆☆ Level 2 of 5
Prove that in any group of \(6\) people, two have the same number of acquaintances inside the group.
Possible numbers are \(0\) to \(5\), but \(0\) and \(5\) cannot both occur.
Each person has \(0\) to \(5\) acquaintances. If someone has \(0\), no one has \(5\); if someone has \(5\), no one has \(0\). Thus at most \(5\) values are possible for \(6\) people. By pigeonhole, two values coincide.
Nonstandard boxes: graph degrees.