### 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 2k-1 ≤ n < 2k, then f(n) = k.

Solution

Take k so that 2k-1 ≤ n < 2k. Then, adding leading zeros as necessary, we can write n as a k digit binary number. Let Ai 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 Ai 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 Ai 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 Ai. That gives 2h - 1 possible classifications (-1 because an element must be in at least one Ai) and no two elements can have the same classification. Hence n ≤ 2h - 1. So 2k-1 <= 2h - 1 and hence k ≤ h, so k ≤ f(n).