XXV OBM

Question

Let S be a set with n elements. Take a positive integer k. Let A_1, A_2, , A_k be any distinct subsets of S. For each i take B_i = A_i or B_i = S - A_i. Find the smallest k such that we can always choose B_i so that _1 i k B_i = S.

Accepted Answer

The 2^k sets C_1 C_2 C_k, where C_i = A_i or C_i = S - A_i, are all disjoint. If 2^k > n, it follows that one of them must be empty. Hence its complement (which is D_1 D_2 D_k, where D_i = S - A_i), is S. On the other hand if 2^k = n, then we can choose k subsets A_i such that all 2^k intersections are non-empty. That means all possible unions are incomplete. Thus the answer is the smallest k such that 2^k > n.