Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
    
In fact the 10 can be reduced to 9 and the 20 can be reduced to 18. See Ramsey's theorem –  Henry Oct 17 '12 at 0:19
add comment

1 Answer

up vote 5 down vote accepted

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.

share|improve this answer
    
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. –  Henry Oct 17 '12 at 0:15
    
@Henry, I think that's implied in Brian's saying the argument with 10 enemies is entirely similar. –  Gerry Myerson Oct 17 '12 at 0:22
    
@Henry: Yes it does $-$ but like Gerry, I consider that ‘entirely similar’. –  Brian M. Scott Oct 17 '12 at 0:27
    
@Gerry, Brian, I accept that, but less informed readers might not realise that reflection works on the given information –  Henry Oct 17 '12 at 0:29
1  
@user1038665: You’re welcome. –  Brian M. Scott Oct 17 '12 at 2:05
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.