MathDB

Distinct subsets with at most n/2 elements

Source: Iran PPCE 2004

January 9, 2009

combinatorics proposedcombinatorics

Problem Statement

Let A\equal{}\{A_1,\dots,A_m\} be a family distinct subsets of

\{1,2,\dots,n\}

with at most

\frac n2

elements. Assume that

A_i\not\subset A_j

and

A_i\cap A_j\neq\emptyset

for each

i,j

. Prove that: \sum_{i\equal{}1}^m\frac1{\binom{n\minus{}1}{|A_i|\minus{}1}}\leq1