For $n$ people, if it is known that (a) there exist two people knowing each other among any three people, and (b) there exist two people not knowing each other among any four people. Find the maximum of $n$. Here, we assume that if $A$ knows $B$, then $B$ knows $A$.
Problem
Source: CWMO 2005-8
Tags: Ramsey Theory, combinatorics unsolved, combinatorics, graph theory
22.02.2006 14:15
Anybody?
22.02.2006 19:58
Hint: try to use Turan's theorem
31.05.2006 05:34
my solutioonn :n$\leq 9$
05.01.2008 05:27
can someone post a full solution?
17.01.2008 23:31
This is asking for the value of the ramsey number R(3,4) it is 9 so the maximum wanted is 8. You can search the web for proof of this.
04.02.2009 18:50
we will prove that $ 8\ge n$ (*)if someone A knows at least 6 people, by Ramsey's theorem, there exist 3 people among them who dont know each other in every three students, or there exist 3 people they know each other. A and the three people form a group of four people such that every two of them know each other. contradiction (**)if some one A knows at most n-5 people, then in the remaining there are at least 4 people, none of knows A. Thus every two of the four people know each other, contradiction. when $ n\ge10$ one of (*) and (**) must occur if $ n = 9$ in order to avoid (*) and (**), each person knows exactly 5 pther people. Thus the number of pairs knowing each other make a contradiction.This contradiction implies $ 8\ge n$.Hence, the maximum value is 8.
02.07.2020 21:52
Here is the picture for $n=8$ (my sol is the same as aboves): Here, where $A_1 , A_2 , \dots, A_8$ represent the $8$ students. The line segment between $A_i$ and $A_j$ means $A_i$ and $A_j$ know each other.