THE 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}}^{\prime }=\{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^{\prime }$ in $X$ is covered by a single member of $B_x$. In other words, there is a single set in $\mathcal{B}$ covering $x^{\prime }$ but not $x$. In this case, draw an arrow from $x$ to $x^{\prime }$. 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 \cdots \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^{\prime }=\{x_1,x_2,\dots ,x_k\}$. Remove $A_1,A_2,\dots ,A_k$ from $\mathcal{B}$ to obtain a collection ${\mathcal{B}}^{\prime }$ each member of which either contains or is disjoint from $X^{\prime }$: for if a member $B$ of ${\mathcal{B}}^{\prime }$ contained some but not all elements of $X^{\prime }$, 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^{\ast }$ outside $X$ and let $$B^{\ast }=\{B:B\in B^{\prime },B\cap X^{\prime }=\varnothing \}\cup \{(B\setminus X^{\prime })\cup \{x^{\ast }\}:B\in B^{\prime },X^{\prime }\subseteq B\};$$ thus, in each member of $B^{\prime }$ containing $X^{\prime }$, the latter is collapsed to singleton $x^{\ast }$. Notice that $B^{\ast }$ is a collection of proper non-empty subsets of $X^{\ast }=(X\setminus X^{\prime })\cup \{x^{\ast }\}$, no subcollection of which is tight. By the induction hypothesis, $|B^{\prime }|=|B^{\ast }|\le 2|X^{\ast }|-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^{\prime }\in C}{C}^{\prime }$ 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}}^{\prime }$ (then $|{\mathcal{B}}^{\prime }|=|\mathcal{B}|$). We claim that ${\mathcal{B}}^{\prime }$ is good. Assume, to the contrary, that ${\mathcal{B}}^{\prime }$ 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}}^{\prime }$ 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}}^{\prime }=\mathcal{B}\setminus (\mathcal{C}\cup \{B\})$. By the argument above, each set in ${\mathcal{B}}^{\prime }$ contains either both $x$ and $y$, or none of them. Collapse $\{x,y\}$ to a singleton $x^{\ast }$ to get a new collection of $|{\mathcal{B}}^{\prime }|\ge |\mathcal{B}|-2$ subsets of $(X\setminus \{x,y\})\cup \{x^{\ast }\}$ containing no tight subcollection. By the induction hypothesis $|{\mathcal{B}}^{\prime }|\le 2(n-1)-2$, so $|\mathcal{B}|\le 2n-2$.