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.
Problem
Source: Bosnia and Herzegovina TST 2013 problem3
Tags: inequalities, induction, combinatorics proposed, combinatorics
20.05.2013 20:45
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 ...
20.05.2013 21:38
It is maybe bad idea but noone managed to solve this problem.
20.05.2013 22:49
Precisely ... pointless.
22.05.2013 07:32
Isn't noone knows noone the same thing as everyone knows everyone?
22.05.2013 11:51
Obviously, NOT
15.12.2013 04:05
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.
15.12.2013 05:17
The Erdos-Szekeres theorem says nothing about this problem.
02.02.2018 21:50
A verbatim copy from pss