MathDB

C2

Part of 2009 Balkan MO Shortlist

Problems(1)

On the Subsets of the sets 1,2,...,n

Source: Balkan MO ShortList 2009 C2

4/6/2020
Let A1,A2,…,AmA_1, A_2, \ldots , A_m be subsets of the set {1,2,…,n}\{ 1,2, \ldots , n \}, such that the cardinal of each subset AiA_i, such 1≤i≤m1 \le i \le m is not divisible by 3030, while the cardinal of each of the subsets Ai∩AjA_i \cap A_j for 1≤i,j≤m1 \le i,j \le m, i≠ji \neq j is divisible by 3030. Prove \begin{align*} 2m - \left \lfloor \frac{m}{30} \right \rfloor \le 3n \end{align*}
combinatoricslinear algebraset theory