Problem

Source: Bulgarian Spring Tournament 2023 12.4

Tags: combinatorics



Given is a set $A$ of $n$ elements and positive integers $k, m$ such that $4 \leq k <n$ and $m \leq \min \{k-3, \frac {n} {2}\}$. Let $A_1, A_2, \ldots, A_l$ be subsets of $A$, all with size $k$, such that $|A_i \cap A_j| \leq m$ for all $i \neq j$. Prove that there exists a subset $B$ of $A$ with at least $\sqrt[m+1]{n}+m$ elements which doesn't contain entirely any of the subsets $A_1, A_2, \ldots, A_l$.