There are six people at a party. Prove that there are three people in this party who know each other, or three people who are complete strangers to each other.

Question

There are six people at a party.  Prove that there are three people in this party who know each other, or three people who are complete strangers to each other.

anonymous · Answer

Looking at one person, he is going to have 5 relationships between the other 5 people, either he will know them, or not. 
By the Pigeonhole Principle, 3 of those relationships will have the be the same.
Now looking at those 3 people connected to the one by the same relationship type, if any of them also have that same relationship, then we have a group of three people that either know each other, or are complete strangers (the original guy, and the two from the group of three that have the same relationship type).
If none of the 3 people have the same relationship type between them, then those three must have the same type.  So there will be a group of 3 people with the same relationship opposite of what the original guy had.

anonymous · Answer

Yes, its a well known problem http://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers

anonymous · Answer

I got it in a problem solving class two semesters ago, it was very interesting.