12. (GDR 3) 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 \subseteq Y$;
(ii) For any three sets $X, Y, Z$ in $F, X \cup Y \cup Z \neq R$.
(iii) $\bigcup_{X \in P} 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 $\mathrm{S}$-families over $R$.
12. 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 \in F$ such that $|X| \geq 5$, then by (3) there exists $Y \in F$ such that $X \cup Y=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 \cup Y \cup Z=R$, which must not happen. Hence we can assume $|X| \leq 4$ for all $X \in F$.
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 combinatorics, the largest number of subsets of a 5-element set of which none is subset of another is $\binom{5}{2}=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 \backslash X \mid Y \in F\}$ and $H=\{Z=Y \cap X \mid Y \in$ $F\}$. Then no two sets in $G$ must complement each other in $R \backslash 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-3=9$. Hence in this case $|F|_{\max }=10$.

In the remaining case all subsets have two elements. There are $\binom{6}{2}=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$.