# Pidgeon hole theorem

• Nov 7th 2006, 11:41 PM
feiyingx
Pidgeon hole theorem
Hi! I was reading an example in my book in the section about pidgeonhole theorem. I hav eno clue what this question is talking about, can someone explain or clarify? Thanks =]

Assume that in a group of six ppl, each pair of individuals consists of two friends or two enemies. Show that there are either three mutual friends or three mutual enemies in the group.

The explanation is: Let A be one of the six ppl. Of the five other ppl in the group, there are either three or more who are friends of A, or three or more who are enemies of A. (Why? wthek) This follows from the pigeonhole principle, since when five objects are divided into two sets, one of the sets has at least 3 elements. In the former case, suppose that B, C, and D are friends of A. If any two of these three individuals are friends, then these two and A form a group of three mutual friends. Otherwise, B, C, and D form a set of three mutual enemies. The proof in the latter case, when there are three or more enemies of A, proceeds in a similar manner.
Why can't there be 4 friends and 2 enemies?

Thanks!
• Nov 8th 2006, 06:11 AM
Plato
“Show that there are either three mutual friends or three mutual enemies in the group.”
In order for the given explanation to be correct, the sentence above must be taken to mean at least three and not exactly three.

“Why can't there be 4 friends and 2 enemies?”
Well there could be. If there are four friends then certainly there are three.
• Nov 8th 2006, 03:22 PM
feiyingx
Thanks. =]