1990 persons
Source: APMO 1990
March 11, 2006
Combinations
Problem Statement
A set of 1990 persons is divided into non-intersecting subsets in such a way that
1. No one in a subset knows all the others in the subset,
2. Among any three persons in a subset, there are always at least two who do not know each other, and
3. For any two persons in a subset who do not know each other, there is exactly one person in the same subset knowing both of them.
(a) Prove that within each subset, every person has the same number of acquaintances.
(b) Determine the maximum possible number of subsets.
Note: It is understood that if a person knows person , then person will know person ; an acquaintance is someone who is known. Every person is assumed to know one's self.