Use the fact that among a group of 10 people, where any two people are either friends or enemies, there are either three mutual friends or four mutual enemies, and there are either three mutual enemies or four mutual friends to show:
Among any group of 20 people, where any two people are either friends or enemies, there are either four mutual friends or four mutual enemies.
I'm unsure on how to approach this problem. How can we use the case of 10 people to generalize the case for 20 people? I've read that if we single out one person, $P_1$, he must have either 10 mutual friends or 10 mutual enemies by the pigeonhole principle. Why is this?
Thank you!
Best Answer
Let $P$ be one of the $20$ people. Let $F$ be the set of people among the other $19$ who are friends of $P$, and let $E$ be the set of those who are enemies of $P$; then $|F|+|E|=19$, since every one of the $19$ is either $P$’s friend or $P$’s enemy. If $|F|$ and $|E|$ were both less than $10$, then we’d have $$|F|+|E|\le 9+9=18\;,$$ which is impossible, so either $|F|\ge 10$ or $|E|\ge 10$. That is, either $P$ has at least $10$ friends in the group, or $P$ has at least $10$ enemies in the group.
Suppose that $P$ has at least $10$ friends in the group. Then $F$ contains either $3$ mutual friends or $4$ mutual enemies. If $F$ contains $4$ mutual enemies, obviously so does the whole group of $20$ people. If $F$ contains $3$ mutual friends, these $3$ people together with $P$ form a group of $4$ mutual friends.
The argument when $P$ has at least $10$ enemies is entirely similar.