Show that in a group of seventeen people, there exists a trio who are either three mutual friends, three mutual enemies, or three mutual strangers.

Question

Suppose that in a group of people that any two people are either friends, enemies of strangers. Show that in a group of seventeen people, there exists a trio who are either three mutual friends, three mutual enemies, or three mutual strangers.

I know I need to use the Generalized Pigeonhole Principle in some way, but I don't know how to turn this into a proof. I assume one of the seventeen to be A for example, then I have sixteen left, group them into three, so the ceiling of $\frac{16}{3}$ which gives me 6. But I don't know how to use 6 to make the proof. Any help would be greatly appreciated.

Answer 1

A has either 6 friends, 6 enemies or 6 strangers. If any two of the six have the matching acquaintance level, you have your three.
Otherwise, the six mutually have only two acquaintance levels, and you do Pigeonhole again.