Show that among any 6 people we can always find 3 people who

Show that among any 6 people we can always find 3 people who know each other OR 3 people who do not know each other.

Solution

This problem is based on Pigeonhole principle:

Consider 6 people represented by dots in a circle. Let every dot is connected to every other dot by a line. Let the lines be the color red if the two people know each other and blue if they do not know each other. Consider any of the 6 dots, say dot X. We can see that X is connected to 5 other dots by a line and by the pigeonhole principle 3 of these lines are of the same color. Now examine the 3 dots connected to X. If any of those 3 people are connected by a red line, then we have found a red triangle which represents 3 people who know each other. If the 3 people are not connected by any red lines, then all 3 of them are connected by blue lines forming a blue triangle which represents 3 people not knowing each other. Thus in a group of 6 people there will always be 3 people who know each other or 3 people who do not know each other.

The pigeonhole principle applies because every person is related to every other person in two ways, either they know the person or they do not. So when we consider any of the 6 people we know that they know 3 people or they don\'t know 3 people.