Tenth ROMANIAN MASTER OF MATHEMATICS

Note. A subset $A$ of $X$ is proper if $A \ne X$. The sets in a collection are assumed to be distinct. The whole collection is assumed to be a subcollection.

First solution. (Ilya Bogdanov) The required maximum is $2n-2$. To describe a $(2n-2)$-element collection satisfying the required conditions, write $X = \{1, 2, \dots, n\}$ and set $B_k = \{1, 2, \dots, k\}$, $k = 1, 2, \dots, n-1$, and $B_k = \{k-n+2, k-n+3, \dots, n\}$, $k=n, n+1, \dots, 2n-2$. To show that no subcollection of the $B_k$ is tight, consider a subcollection $C$ whose union $U$ is a proper subset of $X$, let $m$ be an element in $X \setminus U$, and notice that $C$ is a subcollection of $\{B_1, \dots, B_{m-1}, B_{m+n-1}, \dots, B_{2n-2}\}$, since the other $B$'s are precisely those containing $m$. If $U$ contains elements less than $m$, let $k$ be the greatest such and notice that $B_k$ is the only member of $C$ containing $k$; and if $U$ contains elements greater than $m$, let $k$ be the least such and notice that $B_{k+n-2}$ is the only member of $C$ containing $k$. Consequently, $C$ is not tight.

We now proceed to show by induction on $n \ge 2$ that the cardinality of a collection of proper non-empty subsets of $X$, no subcollection of which is tight, does not exceed $2n-2$. The base case $n=2$ is clear, so let $n > 2$ and suppose, if possible, that $\mathcal{B}$ is a collection of $2n-1$ proper non-empty subsets of $X$ containing no tight subcollection.
To begin, notice that $\mathcal{B}$ has an empty intersection: if the members of $\mathcal{B}$ shared an element $x$, then $\mathcal{B}' = \{B \setminus \{x\} : B \in \mathcal{B}, B \ne \{x\}\}$ would be a collection of at least $2n-2$ proper non-empty subsets of $X \setminus \{x\}$ containing no tight subcollection, and the induction hypothesis would be contradicted.
Now, for every $x$ in $X$, let $B_x$ be the (non-empty) collection of all members of $\mathcal{B}$ not containing $x$. Since no subcollection of $\mathcal{B}$ is tight, $B_x$ is not tight, and since the union of $B_x$ does not contain $x$, some $x'$ in $X$ is covered by a single member of $B_x$. In other words, there is a single set in $\mathcal{B}$ covering $x'$ but not $x$. In this case, draw an arrow from $x$ to $x'$. Since there is at least one arrow from each $x$ in $X$, some of these arrows form a (minimal) cycle $x_1 \to x_2 \to \dots \to x_k \to x_{k+1} = x_1$ for some suitable integer $k \ge 2$. Let $A_i$ be the unique member of $\mathcal{B}$ containing $x_{i+1}$ but not $x_i$, and let $X' = \{x_1, x_2, \dots, x_k\}$.
Remove $A_1, A_2, \dots, A_k$ from $\mathcal{B}$ to obtain a collection $\mathcal{B}'$ each member of which either contains or is disjoint from $X'$: for if a member $B$ of $\mathcal{B}'$ contained some but not all elements of $X'$, then $B$ should contain $x_{i+1}$ but not $x_i$ for some $i$, and $B = A_i$, a contradiction. This rules out the case $k=n$, for otherwise $B = \{A_1, A_2, \dots, A_n\}$, so $|B| < 2n-1$.
To rule out the case $k < n$, consider an extra element $x^*$ outside $X$ and let
$$B^* = \{B: B \in B', B \cap X' = \emptyset\} \cup \{(B \setminus X') \cup \{x^*\}: B \in B', X' \subseteq B\};$$
thus, in each member of $B'$ containing $X'$, the latter is collapsed to singleton $x^*$. Notice that $B^*$ is a collection of proper non-empty subsets of $X^* = (X \setminus X') \cup \{x^*\}$, no subcollection of which is tight. By the induction hypothesis, $|B'| = |B^*| \le 2|X^*| - 2 = 2(n-k)$, so $|B| \le 2(n-k)+k = 2n-k < 2n-1$, a final contradiction.

Second solution. Proceed again by induction on $n$ to show that the cardinality of a collection of proper non-empty subsets of $X$, no subcollection of which is tight, does not exceed $2n-2$.
Consider any collection $\mathcal{B}$ of proper non-empty subsets of $X$ with no tight subcollection; call such a collection good. Assume that there exist $M, N \in \mathcal{B}$ such that $M \cup N$ is distinct from $M, N$, and $X$. In this case, we will show how to modify $\mathcal{B}$ so that it remains good, contains the same number of sets, but the total number of elements in the sets of $\mathcal{B}$ increases.
Consider a maximal (relative to set-theoretic inclusion) subcollection $C \subseteq \mathcal{B}$ such that the set $C = \bigcup_{C' \in C} C'$ is distinct from $X$ and from all members of $C$. Notice here that the union of any subcollection $D \subset \mathcal{B}$ cannot coincide with any $K \in \mathcal{B} \setminus D$, otherwise $\{K\} \cup D$ would be tight. Surely, $C$ exists (since $\{M, N\}$ is an example of a collection satisfying the requirements on $C$, except for maximality); moreover, $C \notin \mathcal{B}$ by the above remark.
Since $C \ne X$, there exists an $L \in C$ and $x \in L$ such that $L$ is the unique set in $C$ containing $x$. Now replace in $\mathcal{B}$ the set $L$ by $C$ in order to obtain a new collection $\mathcal{B}'$ (then $|\mathcal{B}'| = |\mathcal{B}|$). We claim that $\mathcal{B}'$ is good.
Assume, to the contrary, that $\mathcal{B}'$ contained a tight subcollection $\mathcal{T}$; clearly, $C \in \mathcal{T}$, otherwise $\mathcal{B}$ is not good. If $\mathcal{T} \subseteq C \cup \{C\}$, then $C$ is the unique set in $\mathcal{T}$ containing $x$ which is impossible. Therefore, there exists $P \in \mathcal{T} \setminus (C \cup \{C\})$. By maximality of $C$, the collection $C \cup \{P\}$ does not satisfy the requirements imposed on $C$; since $P \cup C \ne X$, this may happen only if $C \subset P$. But then $\mathcal{D} = (\mathcal{T} \setminus \{C\}) \cup C$ is a tight subcollection in $\mathcal{B}$: all elements of $C$ are covered by $\mathcal{D}$ at least twice (by $P$).

and an element of $\mathcal{C}$), and $\mathcal{D}$ and $\mathcal{T}$ both cover all other elements the same number of times – a contradiction. Thus $\mathcal{B}'$ is good.
Such modifications may be performed finitely many times, since the total number of elements of sets in $\mathcal{B}$ increases. Thus, at some moment we arrive at a good collection $\mathcal{B}$ to which the procedure no longer applies. This means that for every $M, N \in \mathcal{B}$, either $M \cup N = X$ or one of them is contained in the other.
Now let $M$ be a $\subseteq$-minimal set in $\mathcal{B}$. Then each set in $\mathcal{B}$ either contains $M$ or forms $X$ in union with $M$ (i.e., contains $X \setminus M$). Now one may easily see that the collections
$$\mathcal{B}_+ = \{A \setminus M : A \in \mathcal{B}, M \subset A, A \ne M\},$$
$$\mathcal{B}_- = \{A \cap M : A \in \mathcal{B}, X \setminus M \subset A, A \ne X \setminus M\}$$
are both good as collections of subsets of $X \setminus M$ and $M$, respectively; thus, by the induction hypothesis, $|\mathcal{B}_+| + |\mathcal{B}_-| \le 2n - 4$.
Finally, each set $A \in \mathcal{B}$ either produces a set in one of the two new collections, or coincides with $M$ or $X \setminus M$. Thus $|\mathcal{B}| \le |\mathcal{B}_+| + |\mathcal{B}_-| + 2 \le 2n - 2$, as required.

Third solution. We provide yet another proof of the estimate $|\mathcal{B}| \le 2n - 2$. Recall the notion of a good collection from Solution 2. Consider any good collection $\mathcal{B}$, and for every $x \in X$ let $\mathcal{B}_x = \{B : B \in \mathcal{B}, x \notin B\}$, as in Solution 1.
Consider an element $x \in X$ such that $|\mathcal{B}_x|$ is maximal. Since the collection $\mathcal{B}_x$ is not tight, and the union of its members does not contain $x$, there exists an element $y \in X$ belonging to a unique member of $\mathcal{B}_x$, say, $B$. Thus, $\mathcal{B}_x \setminus \{B\} \subset \mathcal{B}_y$.
Since $|\mathcal{B}_y| \le |\mathcal{B}_x|$ by maximality of the latter, the collection $\mathcal{C} = \mathcal{B}_y \setminus \mathcal{B}_x$ contains at most one member. Set now $\mathcal{B}' = \mathcal{B} \setminus (\mathcal{C} \cup \{B\})$. By the argument above, each set in $\mathcal{B}'$ contains either both $x$ and $y$, or none of them. Collapse $\{x, y\}$ to a singleton $x^*$ to get a new collection of $|\mathcal{B}'| \ge |\mathcal{B}| - 2$ subsets of $(X \setminus \{x, y\}) \cup \{x^*\}$ containing no tight subcollection. By the induction hypothesis $|\mathcal{B}'| \le 2(n-1) - 2$, so $|\mathcal{B}| \le 2n - 2$.