Olympiad Maths Prep

Library / /3 of 6

Combinatorics Difficulty 6.4 National olympiad Prove it Czech Republic

A family of sets F\mathcal{F} is called *perfect* if the following condition holds: For every triple of sets X1,X2,X3FX_1, X_2, X_3 \in \mathcal{F}, at least one of the sets
(X1X2)X3,(X2X1)X3 (X_1 \setminus X_2) \cap X_3, \quad (X_2 \setminus X_1) \cap X_3
is empty. Show that if F\mathcal{F} is a perfect family consisting of some subsets of a given finite set UU, then FU+1|\mathcal{F}| \le |U| + 1.

Solutions — 2

Solution 1

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

Figure 1
Fig. 2

In the other case, there is at least one set WFW \in \mathcal{F} with yWy \in W, WYW \ne Y (Fig. 2). Due to the choice of the pair (Y,Z)(Y, Z), the set WW can not contain the whole intersection YZY \cap Z (otherwise we would have YWm+1|Y \cap W| \ge m + 1). Let z(YZ)Wz \in (Y \cap Z) \setminus W. We have
y(WZ)Yandz(ZW)Y, 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 X1=Z,X2=WX_1 = Z, X_2 = W, and X3=YX_3 = Y. So this case is not possible and the induction step is concluded.

Solution 2

Again, we proceed by induction with respect to U|U|, with the claim being trivial when U=U = \emptyset. Suppose F\mathcal{F} is a perfect family of subsets of a finite set UU, and let ZZ be a member of F\mathcal{F} of the minimum cardinality among the nonempty ones (if there is no such set, then F1|\mathcal{F}| \le 1 and we are done).
The first observation is that if Y1Y_1 and Y2Y_2 are two nonempty members of F\mathcal{F} that satisfy Y1Z=Y2ZY_1 \setminus Z = Y_2 \setminus Z (possibly Y1=ZY_1 = Z or Y2=ZY_2 = Z), then in fact Y1=Y2Y_1 = Y_2. Suppose otherwise that there exist two such nonempty sets Y1,Y2FY_1, Y_2 \in \mathcal{F} with Y1Y2Y_1 \neq Y_2. Without the loss of generality, suppose that there exists an element x1Y1Y2x_1 \in Y_1 \setminus Y_2. As Y1Y2ZY_1 \setminus Y_2 \subseteq Z, we have that x1ZY2x_1 \in Z \setminus Y_2 (Fig. 3). Since ZZ is of minimum cardinality and Y2Y_2 is nonempty, we have that ZY2|Z| \le |Y_2|. As Z⊈Y2Z \not\subseteq Y_2 (due to x1ZY2x_1 \in Z \setminus Y_2), we infer that also Y2ZY_2 \setminus Z is nonempty, and hence there exists an element x2Y2Z=Y1Zx_2 \in Y_2 \setminus Z = Y_1 \setminus Z. Now observe that
x1ZY2,x2Y2Z,and{x1,x2}Y1. 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 X1=ZX_1 = Z, X2=Y2X_2 = Y_2 and X3=Y1X_3 = Y_1.

Figure 2
Fig. 3

Define a family F\mathcal{F}' of subsets of UZU \setminus Z as follows:
F={YZ:YF,Y}. \mathcal{F}' = \{Y \setminus Z : Y \in \mathcal{F}, Y \neq \emptyset\}.
Clearly, F\mathcal{F}' is a perfect family of subsets of a strictly smaller set, so from the induction hypothesis we infer that FUZ+1|\mathcal{F}'| \le |U \setminus Z| + 1. Moreover, from the observation of the previous paragraph we infer that sets YZY \setminus Z are pairwise different for all YFY \in \mathcal{F} with YY \neq \emptyset, and hence FF+1|\mathcal{F}| \le |\mathcal{F}'| + 1 (the additive +1 comes from possibly having the empty set in F\mathcal{F}). Concluding,
FF+1UZ+1+1U1+1+1=U+1. |\mathcal{F}| \le |\mathcal{F}'| + 1 \le |U \setminus Z| + 1 + 1 \le |U| - 1 + 1 + 1 = |U| + 1.

Looking for a route rather than an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.