Find the maximum number of sets which simultaneously satisfy the following 3 conditions:
(i) any of the sets consists of 4 elements;
(ii) any two different sets have exactly 2 common elements;
(iii) no two elements are common to all the sets.
, 1997
Solution
The maximum number of sets is .
We first assume there are at least sets. WLOG assume and are common elements of at least two sets.
* If there are sets containing both and , say , , , , then all other sets must contain both and . Otherwise a set has to contain (up to renaming of the elements) or , which contradicts condition (i). But now condition (iii) is violated. So this case is not possible.
* If exactly sets contain both and , say , , , then all other sets must contain one of , one of , one of and one of . Consider the following triples of numbers:
At most one triple in each row may be a subset of one of the sets, since otherwise the two sets containing the triples in the same row share at most one element. Therefore, the number of sets is at most , contradiction.
* If exactly sets contain both and , say and , then except , all other sets must contain one of , one of and one of . Consider the following triples of numbers:
Again, at most one triple in each row may be a subset of one of the sets. Therefore, the number of sets is at most , contradiction.
Finally, we can find sets satisfying all the given conditions, for example,
Therefore, the answer is .