Problem

Source: Iranian National Olympiad (3rd Round) 2004

Tags: graph theory, combinatorics proposed, combinatorics



Suppose that $ \mathcal F$ is a family of subsets of $ X$. $ A,B$ are two subsets of $ X$ s.t. each element of $ \mathcal{F}$ has non-empty intersection with $ A, B$. We know that no subset of $ X$ with $ n - 1$ elements has this property. Prove that there is a representation $ A,B$ in the form $ A = \{a_1,\dots,a_n\}$ and $ B = \{b_1,\dots,b_n\}$, such that for each $ 1\leq i\leq n$, there is an element of $ \mathcal F$ containing both $ a_i, b_i$.