International Mathematics Competition
for University Students
2016

IMC2016: Day 1, Problem 4

4. Let $n\ge k$ be positive integers, and let $\mathcal{F}$ be a family of finite sets with the following properties:

(i) $\mathcal{F}$ contains at least $\binom{n}{k}+1$ distinct sets containing exactly $k$ elements;

(ii) for any two sets $A,B\in \mathcal{F}$, their union $A\cup B$ also belongs to $\mathcal{F}$.

Prove that $\mathcal{F}$ contains at least three sets with at least $n$ elements.

Proposed by Fedor Petrov, St. Petersburg State University

Solution 1. 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\gt 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|\gt 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 $\left(\binom{n}{k}+1\right)\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 \left(\binom{n-1}{k-1}+1\right)$ pairs. But $n\cdot \left(\binom{n-1}{k-1}+1\right)\gt (\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|\gt 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\not\in 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\not\in U_1$, and $U_2$ is different from $V$ and $U_1$ because $v_2\in V,U_1$ but $v_2\not\in U_2$.

Solution 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,\ldots$.

Consider a maximal set $I\subset \{1,\ldots,N\}$ such that $A:=\bigcup_{i\in I} S_i$ has size less than $n$, $|A|\lt n$. This means that adding any $S_j$ for $j\notin I$ makes the size at least $n$, $|S_j\cup A|\geq 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}\leq \binom{n-1}{k}\lt N$ distinct $k$-element subsets of $A$, this is a contradiction. So there is at least one $j$ such that $|S_j\cup A|\geq 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$.