Browse · MathNet
PrintSelection and Training Session
Belarus counting and probability
Problem
Given . We call a group of people n-compact if for every person of group one can find n people (different from that person) which are acquainted with each other. Find the maximum possible such that every n-compact group of people contains a subgroup of people acquainted with each other.
Solution
3. See III Silk Road Math. Competition 2004, Problem 4.
Final answer
2n
Techniques
Turán's theoremColoring schemes, extremal arguments