Each of the subsets $ A_1$, $ A_2$, $ \dots,$ $ A_n$ of a 2009-element set $ X$ contains at least 4 elements. The intersection of every two of these subsets contains at most 2 elements. Prove that in $ X$ there is a 24-element subset $ B$ containing neither of the sets $ A_1$, $ A_2$, $ \dots,$ $ A_n$.
Problem
Source: Tuymaada 2009, Junior League, First Day, Problem 4
Tags: algebra, polynomial, calculus, derivative, floor function, combinatorics unsolved, combinatorics
24.07.2009 13:52
Proof: Firstly we can simply assume $ |A_i|=4$ If not,we can repalce $ A_i$ by a $ 4-element$ subset of $ A_i$ We randomly choose $ 24$ element from $ X$ call it $ Y=\{1,2,...24\}$ Of course,$ Y$ may contain some $ A_i$,denote $ m$ by the number of $ A_i$ such that $ A_i$ is contained in $ Y$,($ m$ is obviously finite) All we need to do is to decrease $ m$ WLOG let $ A_1=\{1,2,3,4\}$ contained in $ Y$ We delete $ 1$ can add an element from $ \{25,26,...2009\}$ After deleting $ 1$,$ m$ decrease by at least $ 1$,if we add $ i$ into $ Y$,$ \{i,p,q,r\}$($ i \in \{25,26,...2009\},p,q,r \in \{1,2,...24\}$) isn't any of $ A_i$ Then we are done.So for any $ i \in \{25,26,...2009\}$ $ \exists p,q,r,A_j$ so that $ A_j=\{i,p,q,r\}$ Let us count the possible $ A_j$,It is easily to show there are at most $ \binom{23}{3}$ such $ A_j$(because $ |A_i \cap A_j|\le 2$ and $ |A_j|=4$) but from $ \{25,26,...2009\}$ we are allowed to choose $ 1985$ which is bigger than $ \binom{23}{3}$ Contradiction! QED
27.07.2009 18:33
This is a new song on an old motif (triplets with at most one point in common). Take $ | X | = n \geq 4$, and a maximal cardinality set $ B$ with that property (such sets exist, e.g. any set of at most 3 elements); denote $ | B | = b$. Then for any $ x \in X \setminus B$ there exists at least one set $ x \in A_i$ such that $ A_i \setminus \{ x \} \subseteq B$ (otherwise we can append $ x$ to $ B$). Since $ | A_i \setminus \{ x \} | \geq 3$, one may associate to $ x$ any triplet $ T_x \subseteq A_i \setminus \{ x \}$. For $ y \neq x$, $ y \in X \setminus B$, with set $ A_j$ associated, one has $ T_x \neq T_y$, or else $ | A_i \cap A_j | \geq 3$. Therefore, by counting all possible triplets in $ B$, one has $ | X \setminus B | = n - b \leq \genfrac {(} {)} {0pt} {} {b} {3}$, leading to $ b^3 - 3b^2 + 8b \geq 6n$. This is a strictly increasing polynomial in $ b$ (its derivative is strictly positive), and one checks that $ b \geq \lfloor \sqrt [3]{6n} \rfloor + 1$. For $ n = 2009$ this yields $ b \geq 24$.