Question:
Show that in a group of 10 people (where any 2 are either friends or enemies), there are either 3 mutual friends or 4 mutual enemies, and there are either 3 mutual enemies or 4 mutual friends.
I'm really lost in this question. After hours of just thinking and having no progress, I looked at the answer key, and still lost. So I will give you the books answer key and point out where I'm lost.
Book's Solution:
By symmetry we need to prove only the first statement. Let $A$ be one of the people. Either $A$ has at least four friends, or $A$ has at least six enemies among the other nine people (since $3 + 5 < 9$). Suppose, in the first case, $B, C,D, E$ are all $A$'s friends. If any two of these are friends with each other, then we have found three mutual friends. Otherwise $\{B, C, D, E\}$ is a set of four mutual enemies of $A$. By Example 11, among $B, C, D, E, F, G$ there are either three mutual friends or three mutual enemies, who form with $A$, a set of four mutual enemies.
One can ignore the last sentence, it's basically saying that in 6 people, there are either 3 mutual friends or 3 mutual enemies, which I completely understand already.
My Problem:
The proof actually make sense, except for the part where they said "Either A has at least 4 friends, or A has at least six enemies among the other nine people (since 3 + 5 < 9)", that 's the part thats bothering me. Where did they get the number $4$? I mean, by pigeon hole principle, $A$ has at lest $\lceil \dfrac{9}{2}\rceil = 5$ enemies or friends (not both of course). If you could help me out, I would appreciate it. I'm almost halfway the Discrete Mathematics text book and this is so far the most bizarre, and I would like to build some neural path and make this problem easier.
Best Answer
$A$ has $9$ people who are each friends or enemies. Let's write this as $$F_A+E_A=9.$$
So if $F_A \le 3$ then this implies $E_A \ge 6$.
But since $F_A$ is an integer, $F_A \not \le 3$ implies $F_A \ge 4$.
So we can conclude from $$F_A \le 3 \text{ or } F_A \not \le 3$$ that $$E_A \ge 6 \text{ or } F_A \ge 4$$