Consider a set $S$ of $n$ people such that, for all distinct $x$ and $y$ in $S$, it is the case that either $x$ and $y$ like each other or $x$ and $y$ hate each other. Let us call $S' \subseteq S$ a friend group if, for all distinct $x$ and $y$ in $S'$, $x$ and $y$ like each other, and let us call a $S' \subseteq S$ a hater group if, for all distinct $x$ and $y$ in $S'$, $x$ and $y$ hate each other.
Let us define $R(k)$ as the smallest natural number such that in every set $S$ of $R(k)$ people, there is either a friend group or a hate group of size $k$. For example, $R(2) = 2$.
(a) Prove that $R(3) > 5$.
(b) Prove that $R(3) \leq 6$. (Together with the previous part, we have $R(3) = 6$.)
(c) Prove by induction that $R(k) \leq 2^{(k(k-1))/2}$ for all $k \geq 2$.
I'm having incredible difficulty with this question. I believe that you need to use the generalized pigeonhole principle in solving this but I really am stumped. Any ideas?