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!

  • $\begingroup$ In fact the 10 can be reduced to 9 and the 20 can be reduced to 18. See Ramsey's theorem $\endgroup$
    – Henry
    Oct 17, 2012 at 0:19

1 Answer 1


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.

  • $\begingroup$ I think the argument when P has at least 10 enemies needs an extra step, namely concluding that with 10 people there are either 4 mutual friends or 3 mutual enemies, and that requires a recognition that friends and enemies are essentially equivalent. $\endgroup$
    – Henry
    Oct 17, 2012 at 0:15
  • $\begingroup$ @Henry, I think that's implied in Brian's saying the argument with 10 enemies is entirely similar. $\endgroup$ Oct 17, 2012 at 0:22
  • $\begingroup$ @Henry: Yes it does $-$ but like Gerry, I consider that ‘entirely similar’. $\endgroup$ Oct 17, 2012 at 0:27
  • $\begingroup$ @Gerry, Brian, I accept that, but less informed readers might not realise that reflection works on the given information $\endgroup$
    – Henry
    Oct 17, 2012 at 0:29
  • 1
    $\begingroup$ @user1038665: You’re welcome. $\endgroup$ Oct 17, 2012 at 2:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .