Czech-Polish-Slovak Mathematics Competition

We proceed by induction with respect to $|U|$. If $|U| = 0$, that is, $U = \emptyset$, 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}' = \mathcal{F} \setminus \{Y\}$ are subsets of $U' = U \setminus \{y\}$. Clearly $\mathcal{F}'$, as a subsystem of a perfect system, is perfect as well. Applying the induction hypothesis on $U'$ and $\mathcal{F}'$, we get
$$|\mathcal{F}| = |\mathcal{F}'| + 1 \le (|U'| + 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 \quad \text{and} \quad 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.

Again, we proceed by induction with respect to $|U|$, with the claim being trivial when $U = \emptyset$. 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 \neq 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 \not\subseteq 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, \quad x_2 \in Y_2 \setminus Z, \quad \text{and} \quad \{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}'$ of subsets of $U \setminus Z$ as follows:
$$\mathcal{F}' = \{Y \setminus Z : Y \in \mathcal{F}, Y \neq \emptyset\}.$$
Clearly, $\mathcal{F}'$ is a perfect family of subsets of a strictly smaller set, so from the induction hypothesis we infer that $|\mathcal{F}'| \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 \neq \emptyset$, and hence $|\mathcal{F}| \le |\mathcal{F}'| + 1$ (the additive +1 comes from possibly having the empty set in $\mathcal{F}$). Concluding,
$$|\mathcal{F}| \le |\mathcal{F}'| + 1 \le |U \setminus Z| + 1 + 1 \le |U| - 1 + 1 + 1 = |U| + 1.$$