Skip to main content
OlympiadHQ

Browse · MathNet

Print

Selection 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