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.

I found another question in my text book, it seems simple, but the hardest part is to prove it. Here the question

There are six persons in a party. Prove that either 3 of them recognize each other or 3 of them don't recognize each other.

I heard the answer use Pigeon Hole Principle, but i have no idea in using it. Could somebody please tell me the way to solve it? Thanks for the attention and sorry for the bad English and my messy post

share|improve this question
    
Actually, it is a problem in graph theory. The vertices are the people and if two know each other there is a green edge between them and if they don't they have a red edge between them. Then you need to prove there is at least one unicolor triangle in the graph. –  LinAlgMan May 29 '13 at 11:22
add comment

1 Answer

up vote 5 down vote accepted

NOTE: in my answer I assume that the relation "know someone" is symmetric (i.e., A knows B if and only if B knows A). If this relation is not symmetric for you then, I did not really check it but I believe the statement is not true.\\\

Choose a person A at the party. The following two situations are possible:

(CASE 1) A knows at least three people, say B, C and D, at the party;

(CASE 2) A doesn't know at least three people at the party.

In (CASE 1), if at least a pair among {B,C}, {C,D} or {D,B} is formed by people that know each other, then you have three people that know each other. If there is no such pair among these three, then B, C and D are three people that do not know each other.

In (CASE 2) proceed similarly.

share|improve this answer
    
Thank you, this is obviously easy to understand –  Jake Timberwood May 29 '13 at 12:12
    
+1: It's a fair assumption that it is meant to be symmetric, since it is phrased as "recognize each other". –  Cameron Buie May 29 '13 at 12:30
    
@JakeTimberwood: you are welcome. Let me add that a "pigeon-hole"-argument is used to see that you always have (CASE1) or (CASE2) in my answer. In fact, fixed A, for any person, say B, at the party you have two possibilities (i.e., you can put it in one of two holes): B knows A or B does not know A. As there are 5 people that are not A at the the party, at least 3 people (pigeons?) have to share the same hole. –  Simone May 30 '13 at 7:27
add comment

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.