MathDB

Let

S

be a set of

n>0

elements, and let

A_1 , A_2 , \ldots A_k

be a family of distinct subsets such that any two have a non-empty intersection. Assume that no other subset of

S

intersects all of the

A_i.

Prove that

k=2^{n-1}.

Problem Statement