IMO 1977 LL BUL3

Origin: BUL

Problem

In a company of n persons, each person has no more than d acquaintances, and in that company there exists a group of k persons, k \geqd, who are not acquainted with each other. Prove that the number of acquainted pairs is not greater than [n2/4].

Solution

Let v1, v2, . . . , vk be k persons who are not acquainted with each other. Let us denote by m the number of acquainted couples and by dj the number of acquaintances of person vj. Then m \leqdk+1+dk+2+\cdot \cdot \cdot+dn \leqd(n−k) \leqk(n−k) \leq k + (n −k) 2 = n2 4 .