Let $n$ be an integer greater than 1 and let $X$ be an $n$-element set. A non-empty collection of subsets $A_{1}, \ldots, A_{k}$ of $X$ is tight if the union $A_{1} \cup \cdots \cup A_{k}$ is a proper subset of $X$ and no element of $X$ lies in exactly one of the $A_{i}$ s. Find the largest cardinality of a collection of proper non-empty subsets of $X$, no non-empty subcollection of which is tight.

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

## Alexander Polyansky, Russia
. (Ilya Bogdanov) The required maximum is $2 n-2$. To describe a ( $2 n-2$ )-element collection satisfying the required conditions, write $X=\{1,2, \ldots, n\}$ and set $B_{k}=\{1,2, \ldots, k\}$, $k=1,2, \ldots, n-1$, and $B_{k}=\{k-n+2, k-n+3, \ldots, n\}, k=n, n+1, \ldots, 2 n-2$. To show that no subcollection of the $B_{k}$ is tight, consider a subcollection $\mathcal{C}$ whose union $U$ is a proper subset of $X$, let $m$ be an element in $X \backslash U$, and notice that $\mathcal{C}$ is a subcollection of $\left\{B_{1}, \ldots, B_{m-1}, B_{m+n-1}, \ldots, B_{2 n-2}\right\}$, 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 $\mathcal{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 $\mathcal{C}$ containing $k$. Consequently, $\mathcal{C}$ is not tight.

We now proceed to show by induction on $n \geq 2$ that the cardinality of a collection of proper non-empty subsets of $X$, no subcollection of which is tight, does not exceed $2 n-2$. The base case $n=2$ is clear, so let $n>2$ and suppose, if possible, that $\mathcal{B}$ is a collection of $2 n-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 \backslash\{x\}: B \in \mathcal{B}, B \neq\{x\}\}$ would be a collection of at least $2 n-2$ proper non-empty subsets of $X \backslash\{x\}$ containing no tight subcollection, and the induction hypothesis would be contradicted.

Now, for every $x$ in $X$, let $\mathcal{B}_{x}$ be the (non-empty) collection of all members of $\mathcal{B}$ not containing $x$. Since no subcollection of $\mathcal{B}$ is tight, $\mathcal{B}_{x}$ is not tight, and since the union of $\mathcal{B}_{x}$ does not contain $x$, some $x^{\prime}$ in $X$ is covered by a single member of $\mathcal{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} \rightarrow x_{2} \rightarrow \cdots \rightarrow x_{k} \rightarrow x_{k+1}=x_{1}$ for some suitable integer $k \geq 2$. Let $A_{i}$ be the unique member of $\mathcal{B}$ containing $x_{i+1}$ but not $x_{i}$, and let $X^{\prime}=\left\{x_{1}, x_{2}, \ldots, x_{k}\right\}$.

Remove $A_{1}, A_{2}, \ldots, 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 $\mathcal{B}=\left\{A_{1}, A_{2}, \ldots, A_{n}\right\}$, so $|\mathcal{B}|<2 n-1$.

To rule out the case $k<n$, consider an extra element $x^{*}$ outside $X$ and let

$$
\mathcal{B}^{*}=\left\{B: B \in \mathcal{B}^{\prime}, B \cap X^{\prime}=\varnothing\right\} \cup\left\{\left(B \backslash X^{\prime}\right) \cup\left\{x^{*}\right\}: B \in \mathcal{B}^{\prime}, X^{\prime} \subseteq B\right\} ;
$$

thus, in each member of $\mathcal{B}^{\prime}$ containing $X^{\prime}$, the latter is collapsed to singleton $x^{*}$. Notice that $\mathcal{B}^{*}$ is a collection of proper non-empty subsets of $X^{*}=\left(X \backslash X^{\prime}\right) \cup\left\{x^{*}\right\}$, no subcollection of which is tight. By the induction hypothesis, $\left|\mathcal{B}^{\prime}\right|=\left|\mathcal{B}^{*}\right| \leq 2\left|X^{*}\right|-2=2(n-k)$, so $|\mathcal{B}| \leq 2(n-k)+k=$ $2 n-k<2 n-1$, a final contradiction.