IMC 2016 · Day 1 · P4

If $n = k$ then we have at least two distinct sets in the family with exactly $n$ elements and their union, so the statement is true. From now on we assume that $n > k$.

Fix $\binom{n}{k} + 1$ sets of size $k$ in $\mathcal{F}$, call them `generators'. Let $V \in \mathcal{F}$ be the union of the generators. Since $V$ has at least $\binom{n}{k} + 1$ subsets of size $k$, we have $|V| > n$.

Call an element $v \in V$ `appropriate' if $v$ belongs to at most $\binom{n-1}{k-1}$ generators. Then there exist at least $\binom{n}{k} + 1 - \binom{n-1}{k-1} = \binom{n-1}{k} + 1$ generators not containing $v$. Their union contains at least $n$ elements, and the union does not contain $v$.

Now we claim that among any $n$ elements $x_1, \dots, x_n$ of $V$, there exists an appropriate element. Consider all pairs $(G, x_i)$ such that $G$ is a generator and $x_i \in G$. Every generator has exactly $k$ elements, so the number of such pairs is at most $\bigl( \binom{n}{k} + 1 \bigr) \cdot k$. If some $x_i$ is not appropriate then $x_i$ is contained in at least $\binom{n-1}{k-1} + 1$ generators; if none of $x_1, \dots, x_n$ was appropriate then we wold have at least $n \cdot \bigl( \binom{n-1}{k-1} + 1 \bigr)$ pairs. But $n \cdot \bigl( \binom{n-1}{k-1} + 1 \bigr) > ( \binom{n-1}{k-1} + 1 ) \cdot k$,

so this is not possible; at least one of $x_1, \dots, x_n$ must be appropriate.

Since $|V| > n$, the set $V$ contains some appropriate element $v_1$. Let $U_1 \in \mathcal{F}$ be the union of all generators not containing $v_1$. Then $|U_1| \ge n$ and $v_1 \notin U_1$. Now take an appropriate element $v_2$ from $U_1$ and let $U_2 \in \mathcal{F}$ be the union of all generators not containing $v_2$. Then $|U_2| \ge n$, so we have three sets, $V$, $U_1$ and $U_2$ in $\in \mathcal{F}$ with at least $n$ elements: $V \ne U_1$ because $v_1 \in V$ and $v_1 \notin U_1$, and $U_2$ is different from $V$ and $U_1$ because $v_2 \in V, U_1$ but $v_2 \notin U_2$.

We proceed by induction on $k$, so we can assume that the statement of the problem is known for smaller values of $k$. By contradiction, assume that $\mathcal{F}$ has less than 3 sets with at least $n$ elements, that is the number of such sets is 0, 1 or 2. We can assume without loss of generality that $\mathcal{F}$ consists of exactly $N := \binom{n}{k} + 1$ distinct sets of size $k$ and all their possible unions. Denote the sets of size $k$ by $S_1, S_2, \dots$.

Consider a maximal set $I \subset \{1, \dots, N\}$ such that $A := \bigcup_{i \in I} S_i$ has size less than $n$, $|A| < n$. This means that adding any $S_j$ for $j \notin I$ makes the size at least $n$, $|S_j \cup A| \ge n$. First, let's prove that such $j$ exist. Otherwise, all the sets $S_i$ are contained in $A$. But there are only $\binom{|A|}{k} \le \binom{n-1}{k} < N$ distinct $k$-element subsets of $A$, this is a contradiction. So there is at least one $j$ such that $|S_j \cup A| \ge n$.

Consider all possible sets that can be obtained as $S_j \cup A$ for $j \notin I$. Their size is at least $n$, so their number can be 1 or 2. If there are two of them, say $B$ and $C$ then $B \subset C$ or $C \subset B$, for otherwise the union of $B$ and $C$ would be different from both $B$ and $C$, so we would have three sets $B$, $C$ and $B \cup C$ of size at least $n$. We see that in any case there must exist $x \notin A$ such that $x \in S_j$ for all $j \notin I$. Consider sets $S'_j = S_j \setminus \{x\}$ for $j \notin I$. Their sizes are equal to $k - 1$. Their number is at least $$N - \binom{n-1}{k} = \binom{n-1}{k-1} + 1.$$ By the induction hypothesis, we can form 3 sets of size at least $n - 1$ by taking unions of the sets $S'_j$ for $j \notin I$. Adding $x$ back we see that the corresponding unions of the sets $S_j$ will have sizes at least $n$, so we are done proving the induction step.

The above argument allows us to decrease $k$ all the way to $k = 0$, so it remains to check the statement for $k = 0$. The assumption says that we have at least $\binom{n}{0} + 1 = 2$ sets of size 0. This is impossible, because there is only one empty set. Thus the statement trivially holds for $k = 0$.