### 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.

**Answer**

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