Library / Belarus — Selection and Training Session /15 of 78

Belarus — Selection and Training Session

Combinatorics Difficulty 5.1 AIME, harder Prove it Belarus

Given $n \ge 2$ . 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 $N$ such that every n-compact group of $N$ people contains a subgroup of $n + 1$ people acquainted with each other.

Solution

3. See III Silk Road Math. Competition 2004, Problem 4.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.