29th IMO shortlist 1988/10 solution

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