MathDB
Element belonging to at least n/k subsets

Source: China Second Round 2015 (A) Q2

May 5, 2016
combinatoricsset theory

Problem Statement

Let S={A1,A2,…,An}S=\{A_1,A_2,\ldots ,A_n\}, where A1,A2,…,AnA_1,A_2,\ldots ,A_n are nn pairwise distinct finite sets (n≥2)(n\ge 2), such that for any Ai,Aj∈SA_i,A_j\in S, Ai∪Aj∈SA_i\cup A_j\in S. If k=min⁡1≤i≤n∣Ai∣≥2k= \min_{1\le i\le n}|A_i|\ge 2, prove that there exist x∈⋃i=1nAix\in \bigcup_{i=1}^n A_i, such that xx is in at least nk\frac{n}{k} of the sets A1,A2,…,AnA_1,A_2,\ldots ,A_n (Here ∣X∣|X| denotes the number of elements in finite set XX).
Back to ProblemsView on AoPS