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

Hint: Induction on $k$.

  Solution