Prove that in any group of 6 people there are always at least 3 people who either all know one-another or all are strangers to one-another
- First hint: we need to use the Generalized Pigeonhole Principle for this problem .
- Consider a group of 6 people. Let's draw this: the vertices are people and the lines are connections between the people. We will draw a blue line of the two people know each other and a red line if they don't.
- Consider any person P. Then there are 5 lines coming from the vertex P. How do we use the Generalized Pigeonhole Principle in this set-up? What are the items and what are the boxes?
- Once you figure out the items and boxes, pick a box (without loss of generality) that has either m./n or [m/n] + 1 items depending on what you decide m and n are. Now look at the other vertices connected to P by some line. What can you say from here? Hint: a blue triangle in your picture is a group of 3 people who all know each other and a red triangle is a group of 3 people who all don't know each other.