25th Brazil 2003 Problem A2 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 S - A i . Find the smallest k such that we can always choose B i so that ∪ B i = S.
smallest k such that 2 k > n Solution The 2 k sets C 1 ∩ C 2 ∩ .... ∩ C k , where C i = A i or 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 each D i is chosen to be whichever of A i or S - A i is not C 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. 25th Brazil 2003 © John Scholes jscholes@kalva.demon.co.uk 16 January 2004 Last corrected/updated 16 Jan 04