Show that in any finite gathering of people,there are at least two people who know the same number of people at the gathering(assume that "knowing" is a mutual relationship.)

Question

anonymous · Answer

Sounds like homework.  Good luck!

anonymous · Answer

Let the number of people be n.  I'm assuming a person may know 0 people, and a person can't know themself.  Therefore the minimum number of people a person can know is 0, and the maximum number of people a person can know is n-1.  That's n different numbers.

Now assume that it's possible that everyone can know a unique number of people (the opposite of the conclusion).  Then one person knows 0 people and one person knows n-1 people.  But the person who knows n-1 people must know everyone else, including the person who knows 0 people.  But then that would mean that the person who knows 0 people actually knows 1 person, which is a contradiction.  So the assumption (everyone knows a unique number of people) is false.  Therefore at least two people must know the same number of people.