Problem

Source:

Tags: combinatorics proposed, combinatorics



Suppose that $X$ is a set with $n$ elements and $\mathcal F\subseteq X^{(k)}$ and $X_1,X_2,...,X_s$ is a partition of $X$. We know that for every $A,B\in \mathcal F$ and every $1\le j\le s$, $E=B\cap (\bigcup_{i=1}^{j}X_i)\neq A\cap (\bigcup_{i=1}^{j} X_i)=F$ shows that none of $E,F$ contains the other one. Prove that \[|\mathcal F|\le \max_{\sum\limits_{i=1}^{S}w_i=k}\prod_{j=1}^{s}\binom{|X_j|}{w_j}\] (15 points) Exam time was 5 hours and 20 minutes.