Given any $10$ people in a room, prove that among them there are either $3$ that know each other or $4$ that do not know each other. (Assume that if A knows B, then B knows A.)
Could the pigeonhole principle be used for this? If so, how? I have a feeling it can be used but im not sure where to apply it just yet.
On
It's very simple, let A be an arbitrary person among the 10 people, and denote the other 9 people from $A_1$ to $A_9$.
Case I: A knows at least 4 of $A_i$'s. Then assume A knows $A_1,A_2,\cdots, A_5$.
if $A_i, A_j$ knows each other, then we have a triangle $A, A_i, A_j$. Otherwise, $A_1,\cdots, A_5$ constitutes a set of 5 people that don't know each other
Case II: A doesn't know at least 6 of $A_i$'s. Then consider 6 people $A_1, A_2, A_3,A_4,A_5,A_6$.
Then apply the following lemma shall yield the easy solution:
Lemma There exist three people who mutually know/or don't know each other among 6 random people.
There's a stronger lemma I think you also might want to consider, that is to prove that there are two triangles of people who mutually know/don't know each other.
Choose one of the present people, say $A$. The rest are split into two groups- those that know $A$ (let's say, group $T$) and those that don't (let's say, group $S$). There are just two possibilities: either $|S| ≥ 6$ or $|T| ≥ 4$ (or otherwise $|S∪T| < 9$ which is a contradiction).
If $|S| ≥ 6$, then there has to be $3$ members of $S$ that don't know each other (a well known result). Together with $A$, they form a group of four mutual strangers.
If $|T| ≥ 4$, then either they all don't know each other (in which case we are already done), or some two are acquaintances. In the latter case, together with $A$ these two form a triple of mutual acquaintances.
This completes the proof.