14th Balkan 1997

A collection of m subsets of X = {1, 2, ... , n} has the property that given any two elements of X we can find a subset in the collection which contains just one of the two. Prove that n ≤ 2^m.

Solution

Let the subsets be Y₁, ... , Y_m. Define f: X → {0, 1, 2, ... , 2^m-1} by f(x) = the binary number a₁a₂ ... a_m where the binary digit a_i is 1 iff x belongs to Y_i. Then we claim that if x ≠ y we must have f(x) ≠ f(y). For if f(x) = f(y) then we could not find A_i such that just one of x, y was in A_i (since their binary expansions would agree in the ith digit). So f is injective. But its range has 2^m elements, so its domain cannot have more than 2^m elements. In other words n ≤ 2^m.

Comment. This is almost trivial.

14th Balkan 1997

© John Scholes
jscholes@kalva.demon.co.uk
11 Apr 2002