15th Czech-Polish-Slovak Mathematics Competition

We proceed by induction with respect to $|U|$. If $|U|=0$, that is, $U=\varnothing$, then there exists only one subset of $U$ and clearly $|\mathcal{F}|\le 1$. In the following, let us suppose the statement is true for all sets of cardinality less than $k$ for a given $k>0$. Let $U$ be any set with $|U|=k$ and $\mathcal{F}$ be a perfect family of its subsets. We shall show that $|\mathcal{F}|\le |U|+1$. If $|\mathcal{F}|\le 1$, the claim is obviously true. If $|\mathcal{F}|\ge 2$, consider all the pairs of distinct sets from $\mathcal{F}$. Since the number of such pairs is finite and nonzero, there is a pair $(Y,Z)\in {\mathcal{F}}^2$, $Y\ne Z$, with intersection of maximum cardinality, that is, $|Y\cap Z|=m$ and the intersection of any two distinct sets from $\mathcal{F}$ has at most $m$ elements. Since the sets $Y$ and $Z$ are distinct, at least one of them must contain an element which is not contained in the other. Without the loss of generality let $Y\setminus Z$ be nonempty and take any element $y\in Y\setminus Z$. In the case $Y$ is the only set containing $y$, all the sets from the system ${\mathcal{F}}^{\prime }=\mathcal{F}\setminus \{Y\}$ are subsets of $U^{\prime }=U\setminus \{y\}$. Clearly ${\mathcal{F}}^{\prime }$, as a subsystem of a perfect system, is perfect as well. Applying the induction hypothesis on $U^{\prime }$ and ${\mathcal{F}}^{\prime }$, we get $$|\mathcal{F}|=|{\mathcal{F}}^{\prime }|+1\le (|U^{\prime }|+1)+1=|U|+1,$$ and we are done.

Fig. 2

In the other case, there is at least one set $W\in \mathcal{F}$ with $y\in W$, $W\ne Y$ (Fig. 2). Due to the choice of the pair $(Y,Z)$, the set $W$ can not contain the whole intersection $Y\cap Z$ (otherwise we would have $|Y\cap W|\ge m+1$). Let $z\in (Y\cap Z)\setminus W$. We have $$y\in (W\setminus Z)\cap Y\text{and}z\in (Z\setminus W)\cap Y,$$ which is in contradiction with the property of the perfect system for $X_1=Z,X_2=W$, and $X_3=Y$. So this case is not possible and the induction step is concluded.

---

Alternative solution.

Again, we proceed by induction with respect to $|U|$, with the claim being trivial when $U=\varnothing$. Suppose $\mathcal{F}$ is a perfect family of subsets of a finite set $U$, and let $Z$ be a member of $\mathcal{F}$ of the minimum cardinality among the nonempty ones (if there is no such set, then $|\mathcal{F}|\le 1$ and we are done). The first observation is that if $Y_1$ and $Y_2$ are two nonempty members of $\mathcal{F}$ that satisfy $Y_1\setminus Z=Y_2\setminus Z$ (possibly $Y_1=Z$ or $Y_2=Z$), then in fact $Y_1=Y_2$. Suppose otherwise that there exist two such nonempty sets $Y_1,Y_2\in \mathcal{F}$ with $Y_1\ne Y_2$. Without the loss of generality, suppose that there exists an element $x_1\in Y_1\setminus Y_2$. As $Y_1\setminus Y_2\subseteq Z$, we have that $x_1\in Z\setminus Y_2$ (Fig. 3). Since $Z$ is of minimum cardinality and $Y_2$ is nonempty, we have that $|Z|\le |Y_2|$. As $Z⊈Y_2$ (due to $x_1\in Z\setminus Y_2$), we infer that also $Y_2\setminus Z$ is nonempty, and hence there exists an element $x_2\in Y_2\setminus Z=Y_1\setminus Z$. Now observe that $$x_1\in Z\setminus Y_2,x_2\in Y_2\setminus Z,\text{and}\{x_1,x_2\}\subseteq Y_1.$$ This contradicts the definition of a perfect family for $X_1=Z$, $X_2=Y_2$ and $X_3=Y_1$.

Fig. 3

Define a family ${\mathcal{F}}^{\prime }$ of subsets of $U\setminus Z$ as follows: $${\mathcal{F}}^{\prime }=\{Y\setminus Z:Y\in \mathcal{F},Y\ne \varnothing \}.$$ Clearly, ${\mathcal{F}}^{\prime }$ is a perfect family of subsets of a strictly smaller set, so from the induction hypothesis we infer that $|{\mathcal{F}}^{\prime }|\le |U\setminus Z|+1$. Moreover, from the observation of the previous paragraph we infer that sets $Y\setminus Z$ are pairwise different for all $Y\in \mathcal{F}$ with $Y\ne \varnothing$, and hence $|\mathcal{F}|\le |{\mathcal{F}}^{\prime }|+1$ (the additive +1 comes from possibly having the empty set in $\mathcal{F}$). Concluding, $$|\mathcal{F}|\le |{\mathcal{F}}^{\prime }|+1\le |U\setminus Z|+1+1\le |U|-1+1+1=|U|+1.$$