Each of the subsets A1, A2, …, An 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 A1, A2, …, An.
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 |Ai|=4 If not,we can repalce Ai by a 4−element subset of Ai We randomly choose 24 element from X call it Y={1,2,...24} Of course,Y may contain some Ai,denote m by the number of Ai such that Ai is contained in Y,(m is obviously finite) All we need to do is to decrease m WLOG let A1={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∈{25,26,...2009},p,q,r∈{1,2,...24}) isn't any of Ai Then we are done.So for any i∈{25,26,...2009} ∃p,q,r,Aj so that Aj={i,p,q,r} Let us count the possible Aj,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.