S is a finite set. A set P of subsets of S has the property that any two members of P have at least one element in common and that P cannot be extended (whilst keeping this property). Prove that P contains just half of the subsets of S.
Solution
For any subset X of S, P can contain at most one of X and S-X, so P cannot contain more than half the subsets.
Suppose P contains less than half the subsets. Then for some X, neither X nor S-X are in P. Hence there must be Y in P such that X and Y have no elements in common (otherwise we could extend P to include X). So Y is a subset of S-X. Similarly, P must contain a subset Z of X (otherwise we could extend P to include S-X). But that means Y and Z cannot overlap, contradicting the fact that as members of P they must have an element in common.
© John Scholes
jscholes@kalva.demon.co.uk
25 Jan 2002