MathDB

5

Part of 2004 Pre-Preparation Course Examination

Problems(1)

Distinct subsets with at most n/2 elements

Source: Iran PPCE 2004

1/9/2009
Let A\equal{}\{A_1,\dots,A_m\} be a family distinct subsets of {1,2,…,n} \{1,2,\dots,n\} with at most n2 \frac n2 elements. Assume that Ai⊄Aj A_i\not\subset A_j and Ai∩Aj≠∅ A_i\cap A_j\neq\emptyset for each i,j i,j. Prove that: \sum_{i\equal{}1}^m\frac1{\binom{n\minus{}1}{|A_i|\minus{}1}}\leq1
combinatorics proposedcombinatorics