This is all about the Ramsey numbers $R(r,s)$. The inequality $R(r, s) \leq R(r -1, s) + R(r, s - 1)$ may be applied inductively to prove that $R(r,s) \leq \genfrac {(} {)} {0pt} {} {r+s-2} {r-1}$, says wiki. Therefore $R(n+1,n+1) \leq \genfrac {(} {)} {0pt} {} {2n} {n}$. Very bad idea, to use such well-known results in a selection test ...

It is maybe bad idea but noone managed to solve this problem.

Precisely ... pointless.

Isn't noone knows noone the same thing as everyone knows everyone?

Obviously, NOT

Math-lover123 wrote: Prove that in the set consisting of $\binom{2n}{n}$ people we can find a group of $n+1$ people in which everyone knows everyone or noone knows noone. Erdős–Szekeres theorem. For given r, s they showed that any sequence of length at least (r − 1)(s − 1) + 1 contains a monotonically increasing subsequence of length r or a monotonically decreasing subsequence of length s. can see http://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem We have: Lemma 1: $\left( \begin{array}{l} 2n\\ n \end{array} \right) > {n^2} + 1,\,\forall n \in Z,n \ge 1$ proof We prove by induction, Suppose that $\left( \begin{array}{l} 2n\\ n \end{array} \right) > {n^2} + 1$ We will prove $\left( \begin{array}{l} 2n + 2\\ n + 1 \end{array} \right) > {\left( {n + 1} \right)^2} + 1$ Indeed, $\left( \begin{array}{l} 2n + 2\\ n + 1 \end{array} \right) = \frac{{\left( {2n + 2} \right)!}}{{\left( {n + 1} \right)!\left( {n + 1} \right)!}} = \frac{{\left( {2n} \right)!\left( {2n + 1} \right)\left( {2n + 2} \right)}}{{n!{{\left( {n + 1} \right)}^2}n!}} = \left( \begin{array}{l} 2n\\ n \end{array} \right)\frac{{2\left( {2n + 1} \right)}}{{n + 1}}$ $> \frac{{\left( {{n^2} + 1} \right)2\left( {2n + 1} \right)}}{{n + 1}} > {\left( {n + 1} \right)^2} + 1$ Lemma 2. showed that any sequence of length at least $n^2+1$ contains a monotonically increasing subsequence of length $n+1$ or a monotonically decreasing subsequence of length $n+1$. Proof. Apply by Erdős–Szekeres theorem. when $r=s=n+1$. From Lemma 1 and Lemma 2, we have qed.

The Erdos-Szekeres theorem says nothing about this problem.

A verbatim copy from pss