29th IMO 1988 shortlist Problem 10 Let X = {1, 2, ... , n}. Find the smallest number of subsets f(n) of X with union X such that given any distinct a, b in X, one of the subsets contains just one of a, b.
If 2 k-1 ≤ n < 2 k , then f(n) = k. Solution Take k so that 2 k-1 ≤ n < 2 k . Then, adding leading zeros as necessary, we can write n as a k digit binary number. Let A i be the numbers in X which (when written in binary) have a 1 in place i. That gives us a collection of k subsets. Any number in X must have at least one 1, so the A i have union X. Any two distinct numbers in X must differ in at least one place, so if we take that place to be i, then A i contains just one of the numbers. Thus f(n) ≤ k. Now suppose we have a collection of h subsets which satisfies the condition. We can classify the elements according to whether they are in or out of A i . That gives 2 h - 1 possible classifications (-1 because an element must be in at least one A i ) and no two elements can have the same classification. Hence n ≤ 2 h - 1. So 2 k-1 <= 2 h - 1 and hence k ≤ h, so k ≤ f(n). 29th IMO shortlist 1988 © John Scholes jscholes@kalva.demon.co.uk 30 Dec 2002 Last corrected/updated 30 Dec 02