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