MathDB

16

Part of 1999 Romania Team Selection Test

Problems(1)

Fun sets [3-element subsets of n-element set; [sqrt(2n)]]

Source: Romanian IMO Team Selection Test TST 1999, problem 15; 15-th Iranian Mathematical Olympiad 1997/1998

8/15/2005
Let XX be a set with nn elements, and let A1A_{1}, A2A_{2}, ..., AmA_{m} be subsets of XX such that: 1) ∣Ai∣=3|A_{i}|=3 for every i∈{1,2,...,m}i\in\left\{1,2,...,m\right\}; 2) ∣Ai∩Aj∣≤1|A_{i}\cap A_{j}|\leq 1 for all i,j∈{1,2,...,m}i,j\in\left\{1,2,...,m\right\} such that i≠ji \neq j. Prove that there exists a subset AA of XX such that AA has at least [2n]\left[\sqrt{2n}\right] elements, and for every i∈{1,2,...,m}i\in\left\{1,2,...,m\right\}, the set AA does not contain AiA_{i}. Alternative formulation. Let XX be a finite set with nn elements and A1,A2,…,AmA_{1},A_{2},\ldots, A_{m} be three-elements subsets of XX, such that ∣Ai∩Aj∣≤1|A_{i}\cap A_{j}|\leq 1, for every i≠ji\neq j. Prove that there exists A⊆XA\subseteq X with ∣A∣≥⌊2n⌋|A|\geq \lfloor \sqrt{2n}\rfloor, such that none of AiA_{i}'s is a subset of AA.
floor functionceiling functionquadraticsprobabilityexpected valuecombinatorics unsolvedcombinatorics