Prove that out of nine random people, there can always be found three people who know one another or four people who don't know one another.

Question

Nine people are brought to a meeting (via a specified means of telecommunications, otherwise known as Skype) without any particular patterns. Prove that there can always be found four people who know one another or three people who don't know one another. (They probably didn't enjoy participating in this meeting).

I haven't studied much of combinatorics so this is where I venture into the unknown. I thought of which if one of the required group of people can't be found then the other must be or there doesn't exist nine people such that both of the requirements don't meet. But I'm not sure.

Answer 1

HINTS

I'll just get you started. Suppose some person X knows four of the others, say, A, B, C, and D. If any two of these people, say A and B, know one another, then together with X, they form a group of three mutual acquaintances. But if no two of A, B, C, and D know one another, we have a group of four mutual strangers.

Therefore, we can assume that no one knows at least four of the others, or to put it another way, everyone is a stranger to at least five of the others.

EDIT

The OP states that he inadvertently reversed the numbers on acquaintances and strangers, but I'm not going to bother revising my answer because of this, since it is trivial to adapt the proof.

At bof's suggestion, I'm adding another step. We know that no one knows more that $3$ people. Suppose that everyone knows exactly $3$ people. Then let's count the acquaintanceships. (If A and B know one another, that counts as one acquaintanceship.) If $9$ people have $3$ acquaintances each, that gives $9\cdot3=27$ acquaintanceships, but we have counted each one twice, so we have $27/2=13.5$ acquaintanceships, which is absurd. (Another way of seeing this is with a graph, where the $9$ people are the vertices, and there is an edge between every pair of acquaintances. By the handshaking lemma, there must be an even number of vertices of odd degree.)

Now we know that some person has no more than two acquaintances, so there are at $6$ people (at least) that he doesn't know. Show that among these $6$ there are three mutual acquaintances or three mutual strangers, by arguments similar to those above. Then it's easy to finish.