IMO 1979 SL 12

Origin: GDR

Problem

Let R be a set of exactly 6 elements. A set F of subsets of R is called an S-family over R if and only if it satisfies the following three conditions: (i) For no two sets X, Y in F is X \subseteqY ; (ii) For any three sets X, Y, Z in F, X \cupY \cupZ ̸= R, (iii) % X\inF X = R. We define |F| to be the number of elements of F (i.e., the number of subsets of R belonging to F). Determine, if it exists, h = max |F|, the maximum being taken over all S-families over R.

Solution

The first criterion ensures that all sets in an S-family are distinct. Since the number of different families of subsets is finite, h has to exist. In fact, we will show that h = 11. First of all, if there exists X \inF such that |X| \geq5, then by (3) there exists Y \inF such that X \cupY = R. In this case |F| is at most 2. Similarly, for |X| = 4, for the remaining two elements either there exists a subset in F that contains both, in which case we obtain the previous case, or there exist different Y and Z containing them, in which case X \cupY \cupZ = R, which must not happen. Hence we can assume |X| \leq4 for all X \inF. Assume |X| = 1 for some X. In that case other sets must not contain that subset and hence must be contained in the remaining 5-element subset. These elements must not be subsets of each other. From elementary com- binatorics, the largest number of subsets of a 5-element set of which none is subset of another is
5  = 10. This occurs when we take all 2-element subsets. These subsets also satisfy (2). Hence |F|max = 11 in this case. Otherwise, let us assume |X| = 3 for some X. Let us define the following families of subsets: G = {Z = Y \X | Y \inF} and H = {Z = Y \capX | Y \in F}. Then no two sets in G must complement each other in R \ X, and G must cover this set. Hence G contains exactly the sets of each of the remaining 3 elements. For each element of G no two sets in H of which one is a subset of another may be paired with it. There can be only 3 such subsets selected within a 3-element set X. Hence the number of remaining sets is smaller than 3 \cdot 3 = 9. Hence in this case |F|max = 10.

In the remaining case all subsets have two elements. There are
6  = 15 of them. But for every three that complement each other one must be discarded; hence the maximal number for F in this case is 2 \cdot 15/3 = 10. It follows that h = 11.