MathDB

3

Part of 1977 IMO Longlists

Problems(1)

Inequaity with n people if k >= d [ILL 1977]

Source:

1/11/2011
In a company of nn persons, each person has no more than dd acquaintances, and in that company there exists a group of kk persons, k≥dk\ge d, who are not acquainted with each other. Prove that the number of acquainted pairs is not greater than [n24]\left[ \frac{n^2}{4}\right].
combinatorics proposedcombinatorics